# "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…
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.

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…

@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.