Marching squares

Questions
1

Hello everyone!

I made a simple implementation of the marching squares algorithm for drawing implicit 2d functions.
For anyone that’s not familiar with it wikipedia explains it pretty well here.

Basically it divides the space into a grid and checks the values of the function on every vertex of every square, then based on whether the value at those points is above or below a set threshold (in my case 0) there is a lookup table made of 16 cases with every possible edge.

Here is the playground: Babylon.js Playground

So everything works almost fine, the problem is those horizontal straight lines should not be there, because the function y*tan(y)-x*sin(x) does not approach zero anywhere near those values but grows asymptotically to +/- infinity . You can see that here:
Screenshot (16)

This is because the algorithm sees that on those squares 2 values are above 0 and 2 below so it must go through 0 in between as in case 3 or 12 (table on wiki article)

I can’t think of a way to make it recognize where there is a discontinuity like that…
I thought about checking the difference in magnitude of the values but then a function may as well have very high opposite adjacent values and still go through zero
Can you help me ?

2

I think you can’t do it without knowledge of the function that can have discontinuities and checking specifically for the values at the discontinuities, or more precisely checking that [x, x+d] or [y, y+d] crossed a discontinuity. In your case, you would need to check that [y, y+d] crosses (1+2n)*PI/2:

https://playground.babylonjs.com/#P8NK7V#1

As you said, just checking the sampled points at the corner of the cells is not enough because you will most likely miss the discontinuity.

1 Like
3

Thanks for the answer and the pg :slight_smile:
I guess I’ll ditch marching squares & look for other options to do this