2
$\begingroup$

I'm working on a add-on for Blender, and part of this add-on requires me to calculate the position verts along the arc of an ellipse. At the moment, I'm using the { r_i^2 = (scale_x * cos(theta_i))^2 + (scale_y * sin(theta_i))^2 } equation with a fixed delta to the theta on the arc. This basically, gives you the same thing as if you were to scale a circle by different amounts along the x and y axis.

My issue with this is that the edges along the longer sides of the ellipse are longer than the edges along the shorter side of the ellipse. I want an algorithm that will create edges of (near) equal length.

I could do a binary search for the correct edge length. Yet, this algorithm runs quite often due to the different arcs with different edge counts, so a binary search for edge length might not work so well when I check to see if the edges fit the size of the given ellipse.

I was also thinking about trying the Parallelogram Method. The spacing of the points looks a bit better on the animated-image from Wikipedia, but I also noticed that that the image doesn't quite line up with instructions on creating an ellipse with this method I've managed to find on various sites.

I was wondering if anyone had any advice on fining equally spaced points along an ellipse when all you have are the number of points and the dimensions of the ellipse. I should probable add in that I'm only finding the points along a single quadrant, and I'm using mirroring to find the rest of the points.

$\endgroup$
2
$\begingroup$

There are some posts here https://stackoverflow.com/questions/6972331/how-can-i-generate-a-set-of-evenly-distributed-points-around-an-ellipse and https://mathoverflow.net/questions/28070/finding-n-points-that-are-equidistant-around-the-circumference-of-an-ellipse that may be useful. The eccentricity eqn etc is non-trivial to solve. Might pay to check out whether numpy has this.

Here is a "brute strength" approach that adds up the arc length of every second (as in degrees, minutes, seconds) until we have an arc length approximately the length we desire.

enter image description here

import bpy
import bmesh
from math import sqrt, pi, sin, cos, radians
from mathutils import Vector
def ellipse_point(theta):
    return Vector((a * cos(theta), b * sin(theta)))
a = 4
b = 6
# approximate circumference of an ellipse
C = pi * ( 3 * (a + b) - sqrt((3 * a + b) * ( a + 3 * b)))
print(C)
N = 32 # Number of points per quadrant

d = C / (4 * N) # length of arc
theta = 0
point = ellipse_point(0)
points = [point]
lengths = []
l = 0
dtheta = radians(90.0) / (60 * 60 * N)
while theta <= radians(90):
    theta += dtheta
    v = ellipse_point(theta)
    lengths.append((v - point).length)
    l += (v - point).length    
    if abs(d - l) < 0.001:  
        l = 0
        points.append(point)
    point = v

print("SUM", 4 * sum(lengths))
bm = bmesh.new()
mesh = bpy.data.meshes.new("ellipse")
verts = []
# load in the verts
for p in points:
    pt = (p.x, p.y , 0)
    verts.append(bm.verts.new(pt))
# edges
edges = [bm.edges.new([verts[i-1], verts[i]]) for i in range(1, len(points))]
# close
#bm.edges.new([verts[-1], verts[0]])
bm.to_mesh(mesh)
ellipse = bpy.data.objects.new("ellipse", mesh)
bpy.context.scene.objects.link(ellipse)
mod = ellipse.modifiers.new("mirror", type='MIRROR')
mod.use_y = True
$\endgroup$
  • $\begingroup$ Not every point is going to be interactive, so why waste resources when you can fake the general shape (Mesh menu having a triangle under the name circle)(please look at my latest question to see why/how I ended up finding this answer). Wouldn't it bemore useful to calculate just the vertices that have importance XD such as the intersections. Maybe you could explain in short why this isn't implemented when it's apparently possible, Geogebra is an example, or at least I think that's how it works (because it works). $\endgroup$ – t8ja Jun 21 at 18:49
  • $\begingroup$ t's the same for any other primitive, the edges consist of infinite vertices, but the increments of movement along them are determined.. why wouldn't the same be possible for a circle. Always displaying it as a smooth curve, and pulling up a flag when a limit based on the hardware capability is reached ? Though I doubt that would happen with all the fakery going down uder the hood. $\endgroup$ – t8ja Jun 21 at 19:09
  • $\begingroup$ every irrational value is fakedisplayed. What matters is that it's documented correctly (without even trying to resolve beyond a limit, though that is what is displayed) so other ratios end up being documented and so on $\endgroup$ – t8ja Jun 21 at 19:16
2
$\begingroup$

enter image description here

I propose an adaptive approach :

The idea is to start from the simple x = a * cos(t) and y = b * sin(t).

Then calculate all the distances between the consecutive points, and progressively adapt the angle between them relatively to each distance compared to the average distance.

Note : this is to improve, as the last point (on top in the image below) does not "move". So its own angle does not vary as the others... edit : this note is false. After some tests, this is just matter of setting the good precision to reach (for instance set the precision to 0.00001 and all is ok and needs 6 iterations, so 6 * the amount of vertices calculations).

import bpy, bmesh
from math import radians, sqrt, cos, sin

rad90 = radians( 90.0 )
rad180 = radians( 180.0 )

def createVertex( bm, x, y ): #uses bmesh to create a vertex
    return bm.verts.new( [x, y, 0] )

def listSum( list, index ): #helper to sum on a list
    sum = 0
    for i in list:
        sum = sum + i[index]
    return sum

def calcLength( points ): #calculate the lenghts for consecutives points
    prevPoint = points[0]
    for point in points :
        dx = point[0] - prevPoint[0]
        dy = point[1] - prevPoint[1]
        dist = sqrt( dx * dx + dy *dy )
        point[3] = dist
        prevPoint = point

def calcPos( points, a, b ): #calculate the positions following the angles
    angle = 0
    for i in range( 1, len(points) - 1 ):
        point = points[i]
        angle += point[2]
        point[0] = a * cos( angle )
        point[1] = b * sin( angle )

def adjust( points ): #adjust the angle by comparing each length to the mean length
    totalLength = listSum( points, 3 )
    averageLength = totalLength / (len(points) - 1)

    maxRatio = 0
    for i in range( 1, len(points) ):
        point = points[i]
        ratio = (averageLength - point[3]) / averageLength
        point[2] = (1.0 + ratio) * point[2]
        absRatio = abs( ratio )
        if absRatio > maxRatio:
            maxRatio = absRatio
    return maxRatio

def ellipse( bm, a, b, steps, limit ):

    delta = rad90 / steps

    angle = 0.0

    points = [] #will be a list of [ [x, y, angle, length], ...]
    for step in range( steps  + 1 ) :
        x = a * cos( angle )
        y = b * sin( angle )
        points.append( [x, y, delta, 0.0] )
        angle += delta

    doContinue = True
    while doContinue:
        calcLength( points )
        maxRatio = adjust( points )
        calcPos( points, a, b )

        doContinue = maxRatio > limit
        print( maxRatio )

    verts = []    #edit : to add the edges
    for point in points:
        verts.append( createVertex( bm, point[0], point[1] ) )

    for i in range( 1, len(verts) ):
        bm.edges.new( [verts[i - 1], verts[i]] )


A = 2
B = 1

bm = bmesh.new()

ellipse( bm, A, B, 12, 0.01 )

mesh = bpy.context.object.data      
bm.to_mesh(mesh)
mesh.update()

The algorithm seems to converge (stop) around 4 iterations for a 1% around the mean distance and around 6 iterations to be under 0.01%.

Not very mathematical, but it avoids complex analytical calculations...

(edited : added edges)

$\endgroup$
0
$\begingroup$

Youll porbably have to find the perimeter of the ellipse, and then divide that by how many points you want, so it would be equally spaced?

$\endgroup$
  • $\begingroup$ I was thinking of using one of the upper bound estimation equations as my starting point for the binary search of edge lengths. The real issue would be all the attempts to fit the points onto the perimeter while keeping them equal spaced. The algorithm I've been working on in the back of my mind will tell me if the edge length is too long or short, but fitting them over and over could end up being expensive. $\endgroup$ – Francisco Chavez-Tejeda Aug 8 '16 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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