• Advertisement

Height map terrain + discontinuities

Recommended Posts

I want to create terrain that has sharply defined features, but still has the flexibility of a height map. Though a height map must be defined by a grid, I don't want to terrain to look like a grid. All my previous approaches to this problem tend to look like grids, so now I'm aiming to allow for completely arbitrary discontinuities in the height map. It should be possible to split a cell of the grid between two or more elevations and along curved boundaries. The discontinuities should be independent of the height map grid. Here is a hand-made illustration of the kind of terrain we're aiming for:

GridSpiral.jpg.923d40e6527d89e9aadfc67572d8c19f.jpg

On the left is a curve of discontinuity that has been drawn onto a height map grid. On the right is a rendering of height map terrain that has been split along the same discontinuity curve. Wherever a discontinuity is found, the terrain represents a difference in elevation by a vertical wall instead of the usual slope. The idea is to get an automated system for putting this sort of terrain into a game.

I have considered allowing the discontinuities to be an unrestrained set of line segments with floating-point 2D vertices. We'd have total freedom to draw any discontinuities we could imagine, such as splitting a single grid cell into a dozen pieces. This introduces many complexities, such as forcing us to use procedural triangulation to determine how each cell should be rendered. Here is a link to a pdf guide to the Ear Clipping algorithm which we might use for this triangulation: Triangulation By Ear Clipping

It also makes navigating the terrain tricky. At a minimum we need to determine if one of the player's moves would cross a discontinuity. That in itself is not too hard, but we wouldn't want the player to be stopped dead just by brushing a discontinuity. We want the player to slide along these barriers when appropriate, and the math behind doing that is not at all obvious. We also need a way for computer-controlled enemies to navigate this world, perhaps by automatically generating a navigation mesh.

Perhaps the problem should be simplified by restricting the discontinuities in ways that have no significant impact on the resulting terrain. We don't particularly want a cell to be split into a dozen pieces, so maybe there should be a limit to how many discontinuities can pass through a single cell. We might be limited to certain vertices within each cell, such as a vertex on each corner, a vertex somewhere on each edge, and a 9th vertex floating somewhere in the interior of the cell. With that sort of restriction, triangulation should be greatly simplified.

What sort of algorithms and approaches would you use to create this effect? Are there any other ways to simplify the problem?

Share this post


Link to post
Share on other sites
Advertisement

I think all of those problems have already been solved.

Automatic navigation meshes are covered by all kinds of examples online, and they work well especially if you add a margin around the areas. Capsule collision shapes allow easier physics sliding along the boundaries and slopes. There really shouldn't be an issue with multiple discontinuities in the cell, unless it interferes with some other aspect of your system.

 

Share this post


Link to post
Share on other sites
5 minutes ago, frob said:

I think all of those problems have already been solved.

Does that mean you'd go ahead with implementing the full unsimplified plan, ear clipping and all? All of this is sufficiently easy that there's no reason to look for an easier way?

Share this post


Link to post
Share on other sites

Depends on the skill level and experience of the developers.

For me personally, I would have no problem implementing that as described:  Start with a regular grid for your terrain mesh. Subdivide along those curves -- it doesn't need to be that specific algorithm as there are many good ones -- and avoid T-junctions which cause cracks. Adjust heights and add triangle strips along the wall edges. Create a 2D navigation mesh for both player and AI by starting with your curve image, expanding a margin around the (a one-pass kernel operation), and using that image or map directly as a 2D grid. Maybe adjust the image around the ends of lines if you want to enable a slight hop over them. Add object footprints as necessary for world items, again use that same image or map for the starting point to add object footprints in 2D.  

I've done each of those tasks before on various projects, none are particularly difficult if you're already comfortable manipulating meshes and grids. Did I miss any steps of your project?

If there are any steps in there you (or the people building the system) don't fully understand it will take reading, but all of them are solved problems.

Edited by frob
Spelling.

Share this post


Link to post
Share on other sites

Incidentally, a quick image from a demo tool from about 20 years ago. Polygonal cuts without cracks has been solved for decades.This demo tool happens to divide in regular triangles, but you can cut along any arbitrary line. I mouse-drew your path, but you could do it along any length you want, not just a regular grid.

TIN_subdivision.PNG.b1e4a10c6dabb2ce5632c3fe6b736bd5.PNG

Share this post


Link to post
Share on other sites
35 minutes ago, frob said:

Subdivide along those curves -- it doesn't need to be that specific algorithm as there are many good ones -- and avoid T-junctions which cause cracks.

This seems to be recommending something quite different from ear splitting. It looks more like a quadtree based implementation. At least that's what I think of first when I see the word "subdivide" and the image you provided. For example, I've created an illustration showing a single grid cell that has been subdivided by quadtree around a curve.

CurveSubdivide.jpg.87095df1171d379250b3091048f98478.jpg

The curve is in blue. The black lines are the new squares that have been inserted to subdivide the cell. The gray lines represent the special triangulation that we'd do to eliminate T-junctions. I've included additional subdivisions to make sure that no square is subdivided more than one level deeper than its neighbors so we only have to deal with a few possible types of T-junction.

This raises a question: How far do we subdivide? The algorithm could subdivide forever and never exactly reach the curve. Even just trying to get close to the curve would seem to cause an explosion in the number of triangles in the mesh. Using diagonals across the corners of the squares helps, but even in the image you supplied it looks like jagged curve following a grid.

54 minutes ago, frob said:

Create a 2D navigation mesh for both player and AI by starting with your curve image, expanding a margin around the (a one-pass kernel operation), and using that image or map directly as a 2D grid.

I was planning to store the curves as line segments, but this seems to be suggesting we use a raster image exclusively. At least I've only ever heard of kernel operations being applied to rasters. Rasters are enticing in their simplicity, but I worry that we'd have no way to determine the slope of curve, and I was hoping to use the slope of the curve to implement the player sliding along walls.

Perhaps the idea is to use the capsule collision shape to enable sliding even without any slope information for the walls. But in that case, wouldn't we want to avoid expanded margins? It seems the point of margins is so we can do collisions against just the centers of moving objects instead of having to worry about collision shapes, but we'll want to detect collisions before they reach the center of the object in order to do angle calculations. Here's an illustration:

CircleCollision.jpg.e9606e819431392a1de4073342cad0bf.jpg

The blue curve is the wall. The black curve is the capsule collision shape that is colliding with the wall. The blue arrows show the direction from the center to the detected collisions. The red arrow is the direction the player is trying to move. The black arrow is the actual movement, perpendicular to the collision direction that's closest to the player's intended movement so we avoid going through the wall while still making progress in roughly the player's intended direction. Does this sound right?

1 hour ago, frob said:

Did I miss any steps of your project?

That seems to cover everything, but more details are always appreciated.

Share this post


Link to post
Share on other sites
4 hours ago, Outliner said:

It looks more like a quadtree based implementation.

As I wrote:

5 hours ago, frob said:

This demo tool happens to divide in regular triangles, but you can cut along any arbitrary line.

There have been tools and algorithms to build TIN's for over 40 years, and T-joint preventing algorithms for at least 30 of those years. It takes slightly more work to modify the mesh, but still very easy if you are comfortable with mesh manipulation.

Share this post


Link to post
Share on other sites
7 minutes ago, frob said:

This demo tool happens to divide in regular triangles, but you can cut along any arbitrary line.

What does that mean exactly? It's nice that the tool allows that, but it would be even nicer if we had access to that tool or the algorithm that it uses. How does it allow us to cut along any arbitrary line? Are we talking about using regular triangles to approximate arbitrary lines? Does the algorithm that it uses have a name?

9 minutes ago, frob said:

There have been tools and algorithms to build TIN's for over 40 years.

It's nice to know how old algorithms are, but it would be more useful to know the names of the algorithms so we can look them up and get details.

Share this post


Link to post
Share on other sites

I'm very sorry, I forgot that this was in For Beginners.

I thought this was in the General/Gameplay forums, where people are generally assumed to have more knowledge and experience.  When you wrote lines like "the terrain we're aiming for", "We'd have total freedom", and other "we" statements it seemed you were working with an experienced group. As it is for beginners, I'll try to keep it simple. Everyone starts somewhere.

Going through each. Apologies if something feels too basic or too advanced, I'm not sure what skill levels you are at.

Staring with a mesh for the terrain, you can begin with whatever polygonal mesh you want, usually people use triangles on a regular grid. With the shape you're describing you will probably not use a regular mesh. You can find many different data structures by searching for "triangular irregular mesh", there are many different structures with their own pros and cons.  

It looks like you've already got the point about T-junctions. They tend to introduce small holes and gaps.  These are easy to avoid and there are many different techniques. Subdividing a triangle has a few approaches, usually either a subdivision in the middle breaking it into three pieces, or dividing any side of the triangle. Another approach is to turn an edge into multiple fans, but the math is a bit more complex. There are different reasons to split on either side versus splitting in the center, and some algorithms do both.  For search terms try: triangle surface loop subdivision algorithms, triangle mid-edge subdivision algorithms, triangular mesh butterfly algorithms, and triangular mesh sqrt(3) algorithms. There are many others developed over the decades, but those should help explain how it is done and the reasons to pick each one.  Some of the algorithms are extremely simple and produce good results quite rapidly, some produce fewer polygons, some produce denser polygons useful for sub-pixel effects.

I know the image I posted used a regular grid, and I'm wondering if it would have been better not to post that.  Again, you can use any arbitrary slice.  I've seen tools that approximate a curve by using a triangle fan with many narrow steps. They step along the curve to find points along it within the triangle, then use those points to build the dense fan, then run a check to correct for T-junctions.

You ask how far to subdivide, and that one really is up to you.  Except for straight parametric lines, a parametric curve can never be perfectly represented in polygons.  If you split on an irregular pattern you can approximate the curve as much as you'd like. I noticed the Ear Clipping routine you posted doesn't work with a parametric curve but with known polygon points. In theory you could continue subdividing a curve with multiple vertices per pixel. There are algorithms that will do that, called subdivision surfaces, useful when looking at sub-pixel accurate effects.  They're rarely used to the sub-pixel level in games except in rare cases with lighting shaders and such, but common in movies for various smooth surface effects.  Consider a sphere as a good example: A sphere may be broken down as 20 points, 50 points, even 10000 points, but current rendering technology with pixels doesn't render a sphere as a smooth curve. You may use sub-pixel accuracy in order to get the pixel to have highly accurate coloration or anti-aliasing, but ultimately it is still a square pixel and not a curve.

Once the polygons are simplified on the x/z or x/y plane (depending on what axis you are using) then adding height is straightforward.  Since you've already divided the points along the boundary, you duplicate the points along the boundary -- once for the upper level and once for the lower level -- and walk along the two edges with a triangle strip to make the walls. 

With that done, you've got any arbitrary curve as you described, with as much high detail or low detail as you would like.

 

Regarding the navigation mesh, the question comes back to the curve and the navigation engine you are using.  If you are working with a true parametric line then it might be easy or difficult to turn into a collision shape based on the system.  If your system supports parametric surfaces then use it directly. Otherwise, if the system requires line segments or polygons, you are back to the same issue of how much to subdivide. Turning a curve into line segments cannot realistically be done forever, at some point the line must be close enough.  If you're working from an image then you can go up to the individual pixels of the image.  Navigation meshes are typically very coarse, but you can make it as dense as you'd like. Dense grids tend to be more processing work for pathfinding, so consider another pass to remove unnecessary internal points if you're using a polygonal navigation grid.

The comment about processing the terrain navigation as an image with a kernel was one way that many navigation meshes work. Many games use a simple 2D image and encode different areas with different colors or attributes. While it is easy to think of them as colors, the image could hold any information as bits. Perhaps one bit to indicate it can be walked, another to indicate swimming, another to indicate climbing, another to indicate a non-jumping zone, another to indicate slow movement, whatever is needed.  Sometimes they have multiple flags. Sometimes they're combined with other systems, like an audio system to indicate walking on wood or leaves or gravel.  Navigating on a 2D image this way is easy to compute by mapping the character coordinates into an image coordinate and checking the individual cell or the neighbors to the cell.

I mention expanded margins around the barriers/walls because they are commonly used as a safety to prevent passing through a barrier. Performing continuous swept volume tests will detect if you would have passed through the wall, but those are fairly expensive mathematically. It is generally easier to make barriers thick enough that they won't pass through due to numeric drift or big time steps. 

 

Regarding sliding along a wall, I'm not sure what the algorithm is named or if it even has a name.  Basically if you're against a wall or boundary you want to subtract the motion that would push you through the wall. Start by finding the normal of the boundary so you know what way is out. Multiply that direction by the dot product of your velocity and the direction, that will give you the amount of motion that is headed toward the wall.  What remains is the part of the speed headed in the right direction.  In math terms: velocity -= wallNormal *  dotProduct(velocityNormalized, wallNormal).   If you want to preserve speed, which may not feel natural in your game, set the velocity magnitude equal to the original magnitude.  You may also want to do it in two steps, one phase to approach directly to the contact point, then subtract that from your remaining distance; the second phase would use the remaining portion to slide against the wall.

 

Again, I'm very sorry for not paying attention that this was in For Beginners.  Usually there is someone (often moderators like myself) who reminds people to stay on topic in For Beginners and keep it directed to the topic. 

Better?

Edited by frob
Fix some words, it was a long post.

Share this post


Link to post
Share on other sites
13 hours ago, frob said:

You can find many different data structures by searching for "triangular irregular mesh", there are many different structures with their own pros and cons.

That search gives many results and most of them don't seem to be relevant. I'll take your word for it that useful results are in there, but perhaps an example of the sort of thing we're looking for would make it easier to spot the good results.

13 hours ago, frob said:

I've seen tools that approximate a curve by using a triangle fan with many narrow steps. They step along the curve to find points along it within the triangle, then use those points to build the dense fan, then run a check to correct for T-junctions.

It's a bit confusing that we're both building triangles and finding points within "the triangle". If we're talking about a whole fan of triangles, then which triangle is "the triangle"? From the sound of it, I'm guessing that we're building the triangle fan inside another larger triangle. Perhaps a picture is worth a thousand words. Is this the kind of thing we're talking about?

TriangleFanTriangle.jpg.fcec11493f7b4d07b4dcec11239758b4.jpg

The curve is in blue. "The triangle" is in black. The points we found by stepping along the curve are in red. The triangle fans are in gray. I needed more than one triangle fan, which makes me worry that I've got the wrong end of the stick here.

Let's try another guess. When you say triangle fan, perhaps you mean a fan of triangles that is also in the shape of a triangle. So then we'd subdivide one of the edges of "the triangle" and connect the new vertices to the opposite corner of "the triangle," like this:

TriangleFanTriangle2.jpg.c2c1fa94ac45983e563b655644240e91.jpg

Is that more like the triangle fan you're talking about? It ended up creating quite a few quads, so I divided them into triangles with light gray lines.

13 hours ago, frob said:

If you're working from an image then you can go up to the individual pixels of the image.

We keep talking about raster images as if that were a real option. It would be quite a dream to create game levels out of raster images. The level-editing tools would simply be raster image editing tools, both easy to make and easy to use.

Unfortunately in order to render 3D terrain we ultimately need line segments, not pixels. We cannot simply step along a curve made of pixels in a raster the way we can step along a parametric curve. Wouldn't we need some sort of vectorization process to guess the curve that the pixels are supposed to represent? Vectorization seems like more of an art than a science. Here's a link to the wikipedia page on image tracing just to be clear about what we're talking about.

As far as I can tell, there's no way to reliably turn pixels into line segments without making a lot of guesses about what the person drawing the curve was aiming for, and that would lead to artifacts in the rendering of the terrain. Do you have a particular technique in mind? Or do you mean something else when talk about "working from an image"?

13 hours ago, frob said:

I mention expanded margins around the barriers/walls because they are commonly used as a safety to prevent passing through a barrier.

This is a very appealing idea. Instead of creating margins of some solid color, we could fill the margin pixels with vectors pointing to the closest point on the barrier. That way when we check the pixel in the center of the moving object we get both the direction of the barrier and the distance to the barrier, so we can decide if the object is getting too close to the barrier based on the size of the object, and we have a normal vector to use for sliding along the barrier.

Aside from trying to convert an image into a mesh, representing levels as images is a very appealing idea.

Edited by Outliner

Share this post


Link to post
Share on other sites
1 hour ago, Outliner said:

I'll take your word for it that useful results are in there, but perhaps an example of the sort of thing we're looking for would make it easier to spot the good results.

Triangle-by-triangle are easy to understand, but horribly slow for computer data processing.

Arrays of nodes and neighbors are easy to make if you've got triangle strips, and are so-so for single triangles, but otherwise tend to take more space and more processing to do useful things.

Render-friendly collections of triangle strips and fans are convenient to pass to rendering systems, but manipulations can cause them to be expanded or even split into multiple segments. 

Point clouds with edge indices (also called polygon soup) make it easier to break up arbitrary edges or subdivide points, but it comes with complexity. For peak performance the point clouds may need to be re-ordered to give better cache performance or better processing on video cards.  Optimizing these into simpler structures of line strips also takes work.

1 hour ago, Outliner said:

t's a bit confusing that we're both building triangles and finding points within "the triangle". If we're talking about a whole fan of triangles, then which triangle is "the triangle"? From the sound of it, I'm guessing that we're building the triangle fan inside another larger triangle.

Yes, I'm referring to slicing a single large triangle into a bunch of tiny triangles where the path cuts through it. There are many ways to build fans, both of the images you showed can work.  Most of the algorithms avoid triangle fans because the can potentially generate an enormous number of polygons. Depending on what you're doing, they can also mean less processing work since done correctly they don't generate T-junctions. More typically it is a mix of splitting a single edge to create two triangles or breaking one triangle into three.

The list of algorithms mentioned above, loop subdivision, mid-edge subdivision, butterfly, and sqrt(3) families of algorithms, mostly avoid making fans.

1 hour ago, Outliner said:

As far as I can tell, there's no way to reliably turn pixels into line segments without making a lot of guesses about what the person drawing the curve was aiming for, and that would lead to artifacts in the rendering of the terrain. Do you have a particular technique in mind?

There are many, all depending on what your goals are. 

One of the simpler approaches if your line is an actual stroke is an angle squared algorithm. Trace along the pixels of the line. Look at the angle between the previous point, the current point, and the next point. Square the angle, and accumulate it. Squaring it gets rid of the sign for positive/negative angles, and it makes sharper angles far more important.  End the line segment once the accumulated value passes a threshold you figure out experimentally based on your needs. The higher your threshold the more curve can accumulate. If you're worried about overly long segments, you might also include an accumulated line length and end it there.

More advanced methods involve building a curve and fitting it to match. Building splines or Bézier curves that match the picture, or using the least-squares method to fit the curves, they are compute expensive but searches for curve fitting algorithms should find them.

If you don't have the individual strokes, an option is to look for breaklines by running some filters over the image to find curve segments, or for images with less clear boundaries, using gradient descent algorithms to find those segments. They're far more image processing work, but they'll generate strokes for you. Many image processing toolkits have that built in, such as using a Hough Transform to pick out the lines for processing.  Once you have strokes you can use the algorithms above. 

1 hour ago, Outliner said:

Aside from trying to convert an image into a mesh, representing levels as images is a very appealing idea.

It is fairly common.  Most image formats are little more than a fancy 2D array. I've worked on small tile-based games that stored levels as image data, they could encode and compress their levels and metadata using a lossless image format. 

Share this post


Link to post
Share on other sites
4 hours ago, frob said:

One of the simpler approaches if your line is an actual stroke is an angle squared algorithm.

What exactly does "an actual stroke" mean? What sort of line is not an actual stroke? Based on context, I'm going to guess that a stroke is a 1-pixel-wide series of uniformly colored pixels so that for any pixel on the stroke there is a clear next pixel and previous pixel. In contrast, a non-stroke line would be the sort of line often produced by image editors where it is more than one pixel wide and where the color varies due to antialiasing along the edges of the line. Here's an image illustrating my idea of a stroke versus a non-stroke line:

Stroke1.jpg.7a57b266f4f43ff4e347dafc4f0e69f9.jpg

The curve on the left is a stroke and the curve on the right is not a stroke. Correct? I have also marked angles onto a few of the stroke pixels to illustrate my understanding of the angle squared algorithm.

4 hours ago, frob said:

Look at the angle between the previous point, the current point, and the next point.

I'm guessing this means that a straight line through these points is measured as 0-degrees rather than 180-degrees. That way the angle increases as the bend in the line gets sharper, rather then decreasing.

4 hours ago, frob said:

Square the angle, and accumulate it.

What is the accumulation trying to measure? I notice that fairly straight lines can have high accumulations while sharply bent lines can have much lower accumulations. Here is an illustration:

Stroke3.jpg.57baa99e6dd88901186bf066818f9790.jpg

The line on the left makes 45-degree bends when we measure pixel-by-pixel, but overall it is quite straight. This portion of the line has an accumulation of 16200, and that will just keep getting bigger as the line continues on its current straight path. In contrast, the bent line on the right has one 90-degree corner and all zeroes everywhere else, so its accumulation is 8100 and it will stay that low no matter how long it is.

It feels like it would make more sense if we didn't square the angles, so the positive 45s would cancel the negative 45s.

Another issue is in determining which pixel is the next pixel. For example, suppose we wanted 135-degree turn in the line. When we get to the corner there are apparently two pixels which might be considered the next pixel, as illustrated here:

Stroke2.jpg.5e67e6cc0d1c6a6a29c3be9714812a6a.jpg

A similar issue arises when two lines cross each other. This problem should be easy enough to solve by implementing special cases which look ahead more than one pixel and are particularly programmed to recognize intersections and 135-degree corners, but I wonder if I'm on the right track and correctly understanding what you had in mind.

4 hours ago, frob said:

Building splines or Bézier curves that match the picture, or using the least-squares method to fit the curves, they are compute expensive but searches for curve fitting algorithms should find them.

On the contrary, searching suggests this is quite difficult or impossible. This may not have been mentioned specifically, but unlike the illustration I gave in the first post, an actual level in a game should be expected to have more than one curve. Here is a Stack Overflow question on this very topic: fitting multiple curves to set of points. No useful answers ever appeared. The usual content we get when searching for least-squares fitting is how to fit a function to given data, but we're not really looking for a function. We're looking to fit a set of curves to data, and algorithms to achieve that are much harder to come by.

5 hours ago, frob said:

Many image processing toolkits have that built in, such as using a Hough Transform to pick out the lines for processing.

Hough Transform is a fascinating technique. I suspect that if I have to resort to Hough Transform it means that I'm doing something wrong, but if it's a technique that actually gets used in game development than perhaps I should try it. I would love to find a guide on using Hough Transform or similar processes to find lines in images and then turn those images into game level meshes.

Share this post


Link to post
Share on other sites
14 minutes ago, Outliner said:

What exactly does "an actual stroke" mean? What sort of line is not an actual stroke?

Dealing with raw pixel data is difficult for exactly the reasons you mention, which is why I described it as strokes and lines.

Raw pixel data you need to determine how many pixels form a line, they can suffer issues from anti-aliasing, from tiny gaps, from line thickness. You won't know how to proceed when lines intersect each other or touch or otherwise converge. You need to break the pixel data into lines so you know where to segment the terrain.

Image processing tools usually have line detection functionality built in. Some call them line detection. In some processing tools they are called breaklines. Other tools call them other names. Usually the tools reduce the lines they detect into small multi-pixel segments.

If you're looking from a stroke drawn with a pen on a touch-based surface, they produce sample points that are also typically more than one point long.  You can use the stroke data if you have it.

It is far better to rely on an existing image processing library for this rather than to implement all the algorithms yourself.  The only good reason to implement them yourself is if you are trying to learn the algorithms or are doing research on modifying the algorithms.

Rather conveniently, ImageMagick can extract those values with the convert tool and the output is an array of stroke lines. You can use the stroke lines directly if you're using the API, or you can have the convert tool dump the stroke lines in Magick Vector Format (MVF). Example of it for various images is here, although the full color images are far more than what you're looking for with a black and white line.

24 minutes ago, Outliner said:

What is the accumulation trying to measure? I notice that fairly straight lines can have high accumulations while sharply bent lines can have much lower accumulations.

That is exactly the case, yes.  

All those problems you describe are issues if you are dealing with pixel points directly.  That's why I wrote in the earlier replies that you need to deal with strokes, not pixels.  Pixels are the wrong tools.  If you can get stroke points directly from the input device (such as a digital pen) it is easiest. It is more difficult if you must convert pixel data into strokes.

When dealing with stroke points rather than pixels, trying to turn stroke points into well-spaced mesh points means placing the mesh points reasonably far apart. If the points are too close you get a high number of triangles.  Usually (but not necessarily always) the most critical points are the ones around a turn.  You can have an extremely long mesh line when the cut is straight. When you have a gentle curve you want more points.  When you have a sharp angle you want the point of the angle.  If you had a threshold of 2500, then any sharp angle of at least 50 degrees would automatically be a mesh point. A gentle curve may take some distance before reaching the threshold, and a near-perfectly straight line could go a long distance before 

Accumulating angles themselves, such as +45 cancelled by a -45, that means that a wavy line that doesn't quite hit the threshold will constantly cancel itself out, and you'll only have mesh points at the beginning and end of the line. That won't generate a curvy mesh line even though the line is wavy. With the sum of the squares, the sum increases rapidly as the curve begins to bend so a mesh point will be added. During the minima and maxima of the wavy line, the straighter segments will be simplified with very few mesh points.  It generates a nice wavy mesh line, and you can adjust how close the mesh line fits the curve by adjusting the threshold after some experimentation.

That is why it is critical to convert the drawing image into strokes or line segments first.  It is the angle of stroke segments, not the angle of pixels, that tell you where to split your mesh.

34 minutes ago, Outliner said:

Here is a Stack Overflow question on this very topic: fitting multiple curves to set of points. No useful answers ever appeared. The usual content we get when searching for least-squares fitting is how to fit a function to given data, but we're not really looking for a function. We're looking to fit a set of curves to data, and algorithms to achieve that are much harder to come by.

That question is asking something considerably different. They are trying to fit an arbitrary number of curves into arbitrary points.  The answer is correct that there are no good minima. The question is asking for an NP-hard solution (what is the absolute best path, the question is equivalent to the traveling salesman problem) but they want to use a type of curve that will always have the same cost no matter how many of the curves they use, with no conditions of starting point.  It doesn't matter if they use one or ten that they were asking for, the answer is always the same.  Said differently, with 18 points they are asking for a 'best' answer that has about 540 trillion solutions where each answer is nearly identical.

This question here is if you can turn a single strip of pixel points into a single parametric curve.  And the answer there is absolutely yes, even if that means a parametric curve fitted pixel by pixel. A least squares algorithm will quickly generate a tight curve, which is why I would recommend it if you're trying to build your stroke data yourself.  As mentioned I'd prefer to use an existing library for it, but  if you're doing it yourself, the least squares curve fitting to generate your curve strokes will give good results quickly.  Then you're not dealing with pixels, you're dealing with points on a parametric curve, and those can be used with the sum-of-the-squares subdivision method described above.

But you probably won't need to do it.  Just use an existing image processing library like ImageMagick and be done.

53 minutes ago, Outliner said:

I suspect that if I have to resort to Hough Transform it means that I'm doing something wrong, but if it's a technique that actually gets used in game development than perhaps I should try it.

It gets used all the time in image processing for extracting line segments from images.  There is no reason to implement it yourself, just download ImageMagick and use the existing function.  Or if you have another image processing library you prefer, use that and find their edge extraction tools.

 

All this writing about extracting line stroke information from the image.  

Getting back to the big task, use your image processing library to generate the line segments for you, or if you want a challenge do it yourself to learn the math. Create a regular grid as your starting mesh. Step along the lines and use one of the various triangle segmentation algorithms mentioned above, which will start to turn your mesh into polygon soup. Record the points as you traverse the segments. Add height, add walls, turning your mesh into a difficult-to-understand collection of vertices and indeces. Feed the polygon soup into a D3D mesh as a vertex buffer and index buffer. Let D3D optimize the mesh for you. That finishes the visual mesh.

Share this post


Link to post
Share on other sites
1 hour ago, frob said:

Pixels are the wrong tools.  If you can get stroke points directly from the input device (such as a digital pen) it is easiest. It is more difficult if you must convert pixel data into strokes.

This is why I was surprised to see so many suggestions related to raster images. Rasters are nothing but pixels. They are delightfully easy to make, but they never seemed like they would be enough. Naturally we'll make any level editing tools that the game requires, so we'll have stroke points if we want stroke points.

The reason I allowed myself to consider the possibility of using raster-based solutions was because rasters are so much easier to edit. A stroke is easy to create initially by a simple gesture of a pen or mouse, but it gets fiddly if you want to modify it later, like extending it or erasing and replacing part of it. Now that it's clear that the simple raster is not enough, I will need to research user interface solutions to easy stroke editing.

On the other hand, the simplest user interface would be to just let the user edit a raster and find a good library to extract stroke information from the raster. I'm afraid that the library would end up misinterpreting what the user was trying to draw, and the user would end up fighting with the library.

2 hours ago, frob said:

It gets used all the time in image processing for extracting line segments from images.

No doubt that's true, but I'd be surprised if that sort of image processing is often used in game development.

2 hours ago, frob said:

Step along the lines and use one of the various triangle segmentation algorithms mentioned above, which will start to turn your mesh into polygon soup.

It is remarkably hard to find good information about those algorithms on the web. Even so, I think I'm starting to understand. I was confused because I kept focusing on the grid of squares and trying to triangulate each square based on the segments passing through it with complicated techniques like ear clipping.

Now that I ignore the squares and look at each grid cell as being fundamentally a pair of triangles, the problem becomes triangulating a triangle when a segment passes through it, and we only ever need to worry about one segment passing through a triangle, because after the first segment passes through a triangle the triangle gets broken down into smaller triangles. Any future segments will pass through those smaller triangles.

When it is just one triangle and one segment, there are really only 3 very simple cases to consider:

ABC.gif.f2400865dbcc8298b1b4fbb322f76a06.gif

  • A: One endpoint of the segment is inside the triangle. The triangle becomes 4 triangles centered around the endpoint (green) with the segment (blue) running between two of the triangles. Two new vertices are added: the endpoint and a vertex in the edge of the original triangle. Perhaps this is the triangle fan you were talking about and I just didn't understand until now.
  • B: Both endpoints of the segment are in the triangle. We triangulate around the first endpoint (green) to split the existing triangle into 3 new triangles, then we determine which new triangle contains the second endpoint (red) and split that triangle around that endpoint. We just need a new vertex for each endpoint and a total of 5 new triangles.
  • C: The segment passes through the triangle completely. We split the two edges that the segment passes through, turning the triangle into a smaller triangle and a quad, then split the quad into two triangles.

We also need to consider edge cases where segments or endpoints land exactly on existing edges or vertices, but at that point we're just mopping up the details. The above three cases represent the bulk of the problem of splitting an existing mesh along arbitrary curves, and now it seems so easy.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By nick1
      Hello,

      I have limited programming experience in C++, but have always had a passion for games.  Where do I start?  I have a rough idea of the type of game I want to develop and am ready to commit the time necessary to learn new languages.  Are mobile games too difficult to begin with? Should I begin learning the basics of keyboard controls before attempting touch screens?  I would appreciate any input or advice!
      Thanks!
      Nick1
    • By khawk
      Dene Carter, Managing Directory @ Fluttermind LLC (@fluttermind)
      From Indie to Fable and Back. 30 Years of Wisdom.
      Started writing games in 1984 when he was 14 years old. What has he done in 33 years?
      Druid - Commodore 64 Original Dungeon Keeper core team Fable franchise and more Indie through AAA.
      "I am an idiot" - first learned in 1984, and every year after.
      Rockman - made $7500 for 2 weeks of work. Figured he could make 26 games a year, or $438k in today's money.
      Takeaway: Really stupid at 14.
      Even in 1980's, developer only got 12-14% royalties.
      (Side note: Dene is fun to listen to. Recommend this on the Vault when it goes online.)

      You are not your players.
      Made a black and white game on a Spectrum, which was color. Did it because he was poor. Problem is his audience were not poor, and had color TV's. Reviews were not nice. Players see things completely different to you. Do not forget that your players have not seen the game as much as you. Avoid difficulty/complexity-creep. The real world has distractions and beer - they don't care about your game as much as you do. Test your mobile game on the toilet - that's what your real players do. Fundamentally, players live inside their own brains, not yours. Those you ignore will ignore you in return. Design for your players' minds, not for you. Generalizing is Really useful
      "An expert who is too narrow has difficulty colaborationg" - Valve Employee Manual Did a lot of things over the course of his career. Everyone did everything in the 1980's and 1990's. Most developers generalized. Developing a broad skill-set aids communication. Large teams require collaboration and clear communication. Knowledge breeds respect (never say 'JUST'). 'Just' suggests a task is easy. It might not be. Ignorance is an energy. Don't forget you are human. You are designed to adapt and can do anything if you put your mind to it. Be a human. Learn a skill outside your area. Programmer learn how to 3D model. Artist learn how to code. Learn music, theater. Think of yourself as an artist. Rapid Team Growth is Dangerous
      "If your team can eat more than two pizzas, it's too large." Werner Vogels, Amazon VP/CTO Early Fable - 3 developers. Communication very easy. Later Fable, team grew bigger. At 12 people rumor mill started to develop. Can't have everyone in every meeting at same time. Pockets and cliques develop. Fred Brooks. Communication paths don't grow linearly. Team communication grows exponentially. [n * (n-1)] / 2 8 people on team, 28 connections. Ringelmann Effect - "Larger groups lead to less motivation & coordination & productivity." Decreased motivation - larger group, start to feel like a cog in the machine. Decreased coordination - communication pathways explode. Suggestion: Increase identifiability. Make sure everyone knows everyone's contribution. Most of all: think before growing your team. Blandness Has Its Uses
      Pursuit of excellence can be wasteful. Sounds counterintuitive. Blandness helps disguise repetition. Think reusing assets. Players notice the patterns. When asking for something to be made, communicate the context of assets - how will they be seen or heard? Often find they need to be bland. Prototypes Can Be Misleading
      Experiential games are difficult to prototype. More useful for mechanical games. Fable only came together at the very end - threw away at least one entire combat system. Looking back, it wasn't polished not necessarily bad. Bland prototypes are better than ugly ones for experiential. Keep prototype completely separate. Define prototypes success criteria. Art Style is More Important Than You Think
      Curate rather than create Style can hide the fact you can't draw. Restrict complexity. Style is marketing. Unique style tells players there may be something unique about your game. Streamline Your Process
      What is your iteration cost? Recognize your cost to try something and learn from it. Making your life easier is real work. Resist self-sabotage. (context of making tools) Closing Thoughts
      Don't let technology dictate your game's core promise. Static screenshots have to look good, too. No 1 pixel lines. Don't worry about the things people don't ever get to see. Don't panic if your game sucks - fix it. Editor thought: Really enjoyed this talk. Dene is a fun speaker, and his advice was raw, real world advice for anyone aspiring to make it in game development.
    • By Karol Plewa
      Hi, 
       
      I am working on a project where I'm trying to use Forward Plus Rendering on point lights. I have a simple reflective scene with many point lights moving around it. I am using effects file (.fx) to keep my shaders in one place. I am having a problem with Compute Shader code. I cannot get it to work properly and calculate the tiles and lighting properly. 
       
      Is there anyone that is wishing to help me set up my compute shader?
      Thank you in advance for any replies and interest!
    • By Bokchee 88
      I am animator by hard, and i am doing game animation for at least 8 years so far. During the last 2 years, i came with a idea for game and maybe some day, i want to start indie game company. As i am thinking to start game company, i am also thinking what kind of value i can give to the company. For example, am experience in animation,sales(I was selling web development services, before i jumped to gaming), bit of rigging- just not for production, i am learning on the side as well. The rest of the gaming production, like modeling, concept art, texturing, i am total noob or to say better, i am no near interest to do modeling for example, don't have such a patience to do it. But before characters and things are made for animating, what the hell i am would do?
      Also, what is the ideal size of the founding team of a game company? Positions to be filled mostly are, Concept artist, Modeler/Texture artist, programmer, animator-rigger. And later would need more people to join, like more animators, programmers, sound, fx,etc.
       
      And lastly, do i need to have something,like a prototype, to show people and get them interest, or should i ask someone i know, for skill that i lack, for example, Modeling would be great, texturing and rigging, and to start all together from scratch?  
    • By Nikolay Dimchev
      Hello, Game Devs! 
      I am a 3D Modeler and Texture Artist currently looking for freelance work.
      If you're interested please feel free to checkout my portfolio at the link below.
      Contact me with details at nickeydimchev3d@gmail.com!
      ~Nick
      nickeydimchev3d.myportfolio.com
       
  • Advertisement