"Fracturing" meshes

Hello,
I’ve been trying for hours to accomplish this: I want to be able to “fracture” a mesh by giving it a set of points. I don’t know how to explain it, so I’ll give you a really sloppy sketch of what I would like to do…
https://docs.google.com/file/d/0B7Ej3vylOQPLMExvQ3QwbEs1NEE/edit?usp=sharing
Basically, I want to pass in a mesh and a set of points into a function that then returns the mesh I passed in fractured at the points I declared.
If you need more explenation, that would be great.
Thanks in advance.

Unsure if this is a bit more complex, but you may want to look at the Voronoi shatter effect - which often gives a much more pleasing and realistic shatter than simply breaking them up into triangles. These links might be useful:

http://www.joesfer.com/?p=60

http://en.wikipedia.org/wiki/Voronoi_diagram

This might give you a few ideas… :slight_smile:

@andymac3d - Thanks, but it’s not quite the look I’m going for. I’m aiming to get a look the the style Starbucks has with the triangles coloring a shape.

Have a play with this.

function setup()
    tm,pts = createMesh(20)
    parameter.integer("n",3,200,20)
    parameter.boolean("convex")
    parameter.action("Create Mesh",function() tm,pts = createMesh(n,convex) 
        end)
    parameter.watch("math.floor(ElapsedTime)")
end

function createMesh(n,convex)
    local a = 2*math.pi/n
    local r = 200
    local o = vec2(WIDTH,HEIGHT)/2
    local pts = {}
    local lines = {}
    local b
    for k=1,n do
        b = r*math.random()*vec2(1,0):rotate(k*a + .1*math.random()) + o
        table.insert(pts, b)
        table.insert(lines,{b, r*(b-o):normalize() + o})
    end
    local tris 
    if convex then
        tris = decompose(pts) -- convex hull
    else
        tris = decompose(pts,lines) -- non-convex version
    end
    local cols = {}
    local r,g,b = 0,0,0
    local tc = #tris/3
    local cs = 255/math.ceil(math.pow(tc,1/3))
    for k = 1,tc do
        r = r + cs
        if r > 255 then
            r = 0
            g = g + cs
            if g > 255 then
                g = 0
                b = b + cs
            end
        end
        for i=1,3 do
            table.insert(cols,color(r,g,b,125))
            --table.insert(cols,color(255,255,255,125))
        end
    end
    local tm = mesh()
    tm.vertices = tris
    tm.colors = cols
    return tm,pts
end

function draw()
    background(0, 0, 0, 255)
    stroke(238, 153, 5, 255)
    strokeWidth(5)
    --[[
    for k=1,ntri,3 do
        line(tris[k].x,tris[k].y,tris[k+1].x,tris[k+1].y)
        line(tris[k].x,tris[k].y,tris[k+2].x,tris[k+2].y)
        line(tris[k+2].x,tris[k+2].y,tris[k+1].x,tris[k+1].y)
    end
    --]]
    tm:draw()
    for k,v in ipairs(pts) do
        ellipse(v.x,v.y,5)
    end
end

function decompose(pts,lines)
    local npts = {}
    -- create a copy of the points table where each point is
    -- augmented to a table consisting of:
    -- 1. the original point
    -- 2. an empty table which will hold a list of the points
    --    joined to this one
    -- 3. the index of the point
    for k,v in ipairs(pts) do
        table.insert(npts,{v,{},k})
    end
    -- the lens table is a list of all the pairs of points and
    -- the distances between them
    local lens = {}
    for l=1,#npts-1 do
        for m=l+1,#npts do
            table.insert(lens,{npts[l][1]:distSqr(npts[m][1]),npts[l],npts[m]})
        end
    end
    -- we sort this table so that the points with shortest
    -- separations are first
    table.sort(lens,function(a,b) return a[1] < b[1] end)
    -- now we go through the list of pairs and select the lines
    -- from these pairs of points.  We add a line if it does not
    -- cross a line already in the table.  As well as adding the
    -- line to the table of lines, we add each vertex to the
    -- table of the other vertex.  This means that each vertex
    -- ends up with a list of those vertices it is joined to.
    -- By passing in an initial set of lines we can declare some
    -- no-go regions of the shape as new lines will not be added
    -- if they cross the pre-defined lines, but the pre-defined
    -- lines are not used when working out which vertices are
    -- joined, so they become exclusion zones.
    local lines = lines or {}
    local okay
    for _,v in ipairs(lens) do
        okay = true
        for _,u in ipairs(lines) do
            if crossing(v[2][1],v[3][1],u[1],u[2]) then
                okay = false
                break
            end
        end
        if okay then
            table.insert(lines,{v[2][1],v[3][1]})
            table.insert(v[2][2],v[3])
            table.insert(v[3][2],v[2])
        end
    end
    -- For each vertex, we sort the list of adjoined vertices
    -- so that they are listed in cyclic order.  We also adjoin
    -- the first point to the end of the list for simplicity
    for _,v in ipairs(npts) do
        table.sort(v[2],function(a,b) return vec2(1,0):angleBetween(a[1] - v[1]) < vec2(1,0):angleBetween(b[1] - v[1]) end)
        table.insert(v[2],v[2][1])
    end
    -- Now we construct the table of triangles.  Each triangle is
    -- formed by starting with a vertex and taking two of its
    -- adjoining vertices, so long as these two are themselves
    -- adjoined.  To ensure that we only count each triangle
    -- once, we only consider a triangle if our starting vertex
    -- has the lowest index of the three under consideration.
    local tris = {}
    for _,v in ipairs(npts) do
        for k=1,#v[2]-1 do
            if v[3] < v[2][k][3] and v[3] < v[2][k+1][3] then
                okay = false
                for _,u in ipairs(v[2][k][2]) do
                    if u == v[2][k+1] then
                        okay = true
                    end
                end
                if okay then
                    table.insert(tris,v[1])
                    table.insert(tris,v[2][k][1])
                    table.insert(tris,v[2][k+1][1])
                end
            end
        end
    end
    return tris
end
-- this is the tolerance at the end points when checking crossings
local epsilon = 0.01
function crossing(a,b,c,d)
    -- rebase at a
    b = b - a
    c = c - a
    d = d - a
    if b:cross(c) * b:cross(d) > 0 then
        -- both c and d lie on the same side of b so no intersection
        return false
    end
    -- if there is an intersection point, this will be it
    a = (b:cross(d) * c - b:cross(c) * d)/(b:cross(d) - b:cross(c))
    -- does the potential intersection point lie on the line
    -- segment?
    local l = a:dot(b)
    if l > epsilon and l < b:dot(b) - epsilon then
        return true
    end
    return false
end

@Andrew_Stacey - Cool, thanks! (Bookmarked to try to understand later! :-? )

I’ll try it out. Thanks.

Hi @Andrew,

Thanks for this app, I found it very interesting. One feature I find puzzling is the declaration of epsilon outside of a function. I assume this is effectively a global variable but can’t understand why it is not included in function setup()?

How does this method rank versus Delauney Triangulation, I have been looking at triangulation algorithms to add to the LoveCodea library but my maths isn’t up to it.

Thanks,

Bri_G

B-)

@Bri_G The declaration of epsilon outside the function is to make it a once-for-all declaration rather than on a per-case basis. I wouldn’t put it in setup because then it is separated from the function where it is used. I’m also getting used to using toadkick’s cmodule stuff for loading modules whereupon a local declaration like that really is local to that module, so in so far as I was thinking (which isn’t guaranteed - I was on a flight when I wrote this) then I was probably thinking of putting it in a module.

With regard to the Delauney triangulation, then one method of making a Delauney triangulation is to start with an arbitrary one and then do a series of flips. So this could be used as a starting point for such a triangulation but it most definitely is not one. It works by a sort of greedy algorithm: it adds in lines starting with the shortest, and never takes one out if a later one would have been “better”, so it’s possible to end up with some quite thin triangles which might have been better “flipped”. But then the more constraints you add, the longer it takes to create the satisfying object.

However, this is not my area of expertise so I doubt I’ve come up with a particularly efficient algorithm. On the other hand, I think that I’ve come up with a reasonably simple algorithm.