Original Post
🔒 Locked
Marching squares implementation
Advertisement
My advice would be to render your discrete points out into a pixel array (or at least a spatial hash), and the run marching cubes on that. While you can march directly on your data, it will be very inefficient, as you will have to test every point at every step of the algorithm (rather than just the few closest points).
People use "ball-pivoting" algorithms to solve this problem in 3d; I think you could use a "circle-pivoting" algorithm in 2d. Just substitute "circle" for "ball" and "line segment" for "triangle" in the above.
No matter what you do, you'll need to make some assumptions about how close together points need to be in order for you to consider them part of the same surface, and I don't think there's a very principled way to do this unless you have some more information. For ball-pivoting, the decision is how large to make the ball. For swiftcoder's answer, the decision is what resolution to make your occupancy grid. It's different flavors of the same dilemma.
Finally, here's another approach: Make each point have an "influence" around it (e.g., radial b-spline), and define a function as the sum (or maybe product) of these influences. Then, compute the gradient of this function (just the sum of the gradients of the influence functions). You can trace a contour by simulating the following ODE:
dp/dt = R(pi/2) grad(f)(p)
where R(pi/2) is the ninety-degree rotation matrix, and p=(x,y) is a point. You can make this efficient by only using basis functions with compact support (i.e., they're only nonzero over a finite area, unlike, e.g., gaussians. radial b-splines satisfy this), and organizing your points using some kind of spatial hash or tree similar to what swiftcoder suggested. But again with this answer, you run into the same, unavoidable problem: you need to choose "how wide" to make your influence functions.
No matter what you do, you'll need to make some assumptions about how close together points need to be in order for you to consider them part of the same surface, and I don't think there's a very principled way to do this unless you have some more information. For ball-pivoting, the decision is how large to make the ball. For swiftcoder's answer, the decision is what resolution to make your occupancy grid. It's different flavors of the same dilemma.
Finally, here's another approach: Make each point have an "influence" around it (e.g., radial b-spline), and define a function as the sum (or maybe product) of these influences. Then, compute the gradient of this function (just the sum of the gradients of the influence functions). You can trace a contour by simulating the following ODE:
dp/dt = R(pi/2) grad(f)(p)
where R(pi/2) is the ninety-degree rotation matrix, and p=(x,y) is a point. You can make this efficient by only using basis functions with compact support (i.e., they're only nonzero over a finite area, unlike, e.g., gaussians. radial b-splines satisfy this), and organizing your points using some kind of spatial hash or tree similar to what swiftcoder suggested. But again with this answer, you run into the same, unavoidable problem: you need to choose "how wide" to make your influence functions.
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement