main.jl 15.9 KB
Newer Older
1
2
using DataFrames
using CSV
3
using JSON
4
using LightGraphs
5
using NearestNeighbors
6
using Statistics
7
using BenchmarkTools
8
using Plots
9

10

Jayant Khatkar's avatar
Jayant Khatkar committed
11
mutable struct contour
12
13
14
15
16
    pos
    time
end


17
struct contourdata
18
19
20
    contours::Vector{contour}
    G::SimpleDiGraph
    layers::Vector
21
    travel_dists::Dict
22
    layer_height::Number
23
24
25
end


26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct voxmap
    seglen::Vector{Float64}
    segoffset::Vector{Float64}
    segcontours::Vector{Int}
end


struct voxdata
    voxels::DataFrame
    maps::Vector{voxmap}
    below::Vector{Int}
    width::Number
end


41
42
43
44
45
46
47
48
49
50
51
52
53
54
function vecvec_to_matrix(vecvec)
    # convert vector of vectors int a matrix
    dim1 = length(vecvec)
    dim2 = length(vecvec[1])
    my_array = zeros(Float32, dim1, dim2)
    for i in 1:dim1
        for j in 1:dim2
            my_array[i,j] = vecvec[i][j]
        end
    end
    return my_array
end


55
function contour(d::Dict)
56
    return contour(vecvec_to_matrix(d["pos"]), d["time"])
57
end
58

59

60
function contourdata(cons::Vector{contour}, max_layers::Int, min_dist::Number)
61
    G = LightGraphs.SimpleDiGraph(0)
62

63
    # separate contours into layers
64
    layer_heights = sort(collect(Set([c.pos[end,3] for c in cons])))
65
66
67
68
69
70
71
72
73
74
75
76
77
    layers = [[] for i in 1:length(layer_heights)]
    clayeri = []
    contour_trees = []

    # place contours in layers and construct KDTree for each contour
    for i in 1:length(cons)
        l = searchsorted(layer_heights, cons[i].pos[1,3])[1]
        push!(layers[l], i)
        push!(clayeri, l)
        add_vertex!(G)
        push!(contour_trees, KDTree(transpose(cons[i].pos)))
    end

78
    # loop through contours from previous layer and compare waypoints
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
    for i in 1:length(cons)
        l = clayeri[i]

        # add contours from max_layers below
        if l > max_layers
            for c in layers[l-max_layers]
                add_edge!(G, c, i)
            end
        end

        if l == 1 || max_layers == 1
            continue
        end

        for c in layers[l-1]
            # if any points in contour i within min_dist of any points in contour c
            if any([length(b) > 0 for b in inrange(contour_trees[c], transpose(cons[i].pos), min_dist)])
                add_edge!(G, c, i) # mark i dependent on c
            end
        end
    end
100

101
    return contourdata(cons, G, layers, Dict(), layer_heights[1])
102
103
104
105
106
107
end


function seg_helper_orientation(p,q,r)
    val = (q[2]-p[2]) * (r[1]-q[1]) - (q[1]-p[1]) * (r[2]-q[2])
    if val > 0
108
        return 1 # clockwise
109
    elseif val < 0
110
        return 2 # anticlockwise
111
    else
112
        return 0 # colinear
113
114
115
116
    end
end


117
118
119
120
121
122
123
function onseg(p,q,r)
    # check if q lies on segment pr assuming 3 points are colinear
    return ((q[1] <= max(p[1], r[1])) && (q[1] >= min(p[1], r[1])) &&
    (q[2] <= max(p[2], r[2])) && (q[2] >= min(p[2], r[2])))
end


124
125
126
127
128
129
130
function seg_intersect(p1,q1,p2,q2)

    o1 = seg_helper_orientation(p1, q1, p2)
    o2 = seg_helper_orientation(p1, q1, q2)
    o3 = seg_helper_orientation(p2, q2, p1)
    o4 = seg_helper_orientation(p2, q2, q1)

131
132
133
134
135
    if (o1  o2) && (o3  o4) ||
        o1==0 && onseg(p1, p2, q1) ||
        o2==0 && onseg(p1, q2, q1) ||
        o3==0 && onseg(p2, p1, q2) ||
        o4==0 && onseg(p2, q1, q2)
136
137
138
139
140
141
        return true
    end

    return false
end

142

143
144
145
dist(p1, p2) = √sum((p1 -p2).^2)
interpolate(p1, p2, xi, axis) = p1 + (p2-p1)*(xi-p1[axis])/(p2[axis]-p1[axis])
interpolate(p1, p2, x1, xi, x2) = p1 + (p2-p1)*(xi-x1)/(x2-x1)
146

147

148
function voxmap(vox::Vector{Float64}, vox_d::Number, cdata::contourdata)
149
150
151

    # for one vox, get all contours which pass through it
    # only need to search contours in its layer
152
    l = Int(round((vox[3] + cdata.layer_height/2)/cdata.layer_height))
153
154
155
156
    voxx1 = vox[1] + vox_d/2
    voxx2 = vox[1] - vox_d/2
    voxy1 = vox[2] + vox_d/2
    voxy2 = vox[2] - vox_d/2
157

158
    seg_now = false
159
160
161
162
163
164
    seglen = Vector{Number}()
    segoffset = Vector{Number}()
    segcontours = Vector{Int}()
    seglen_sofar = 0
    t_start = 0

Jayant Khatkar's avatar
Jayant Khatkar committed
165
166
167
168
    if l > length(cdata.layers)
        return voxmap(seglen, segoffset, segcontours)
    end

169
    for cid in cdata.layers[l]
170

171
        c = cdata.contours[cid]
172
173
174
175

        # check if contour passes thorough this vox
        for i in 2:size(c.pos)[1]

176
177
178
179
180
            # make sure it is a line segment, not a point
            if c.pos[i-1,1:2] == c.pos[i,1:2]
                continue
            end

181
182
183
184
            # is this line segment completely outside vox?
            if c.pos[i, 1] > voxx1 && c.pos[i-1, 1] > voxx1 ||
                c.pos[i,1] < voxx2 && c.pos[i-1, 1] < voxx2 ||
                c.pos[i,2] < voxy2 && c.pos[i-1, 2] < voxy2 ||
185
                c.pos[i,2] > voxy1 && c.pos[i-1, 2] > voxy1
186

187
                # segment outside vox entirely
188
                if seg_now
189
                    println("Something's gone wrong: segment entirely outside voxel, but last segment inside")
190
191
                end
                continue
192
            end
193

194
195
196
197
            p1inside = c.pos[i-1, 1] < voxx1 && c.pos[i-1, 1] > voxx2 && c.pos[i-1, 2] > voxy2 && c.pos[i-1, 2] < voxy1
            p2inside = c.pos[i, 1] < voxx1 && c.pos[i,1] > voxx2 && c.pos[i,2] > voxy2 && c.pos[i,2] < voxy1
            # is this line segment completely inside vox?
            if p1inside && p2inside
198

199
200
201
202
203
204
                seglen_sofar += dist(c.pos[i], c.pos[i-1]) # append to existing contour
                if !seg_now # start new seg
                    t_start = 0 #  0 bc contour must be starting for this case
                    seg_now = true

                    if i!=2
205
                        println("Whole segment inside but something wrong")
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
                    end
                    continue
                end
            end

            cross_side1 = seg_intersect(c.pos[i-1,:], c.pos[i,:], [voxx1, voxy1], [voxx1, voxy2])
            cross_side2 = seg_intersect(c.pos[i-1,:], c.pos[i,:], [voxx1, voxy1], [voxx2, voxy1])
            cross_side3 = seg_intersect(c.pos[i-1,:], c.pos[i,:], [voxx2, voxy1], [voxx2, voxy2])
            cross_side4 = seg_intersect(c.pos[i-1,:], c.pos[i,:], [voxx2, voxy2], [voxx1, voxy2])

            # does this line segment intersect with vox only once
            if p1inside  p2inside

                # find intersection point
                if cross_side1 || cross_side3
                    # intersection with x
                    xi = [voxx1, voxx2][[cross_side1, cross_side3]][1]
                    p_i = interpolate(c.pos[i-1,:], c.pos[i,:], xi, 1)
                    t_i = interpolate(c.time[i-1], c.time[i], c.pos[i-1,1], xi, c.pos[i,1])
225
                elseif cross_side2 || cross_side4
226
227
228
229
230
231
232
233
234
                    # intersection with y
                    yi = [voxy1, voxy2][[cross_side2, cross_side4]][1]
                    p_i = interpolate(c.pos[i-1,:], c.pos[i,:], yi, 2)
                    t_i = interpolate(c.time[i-1], c.time[i], c.pos[i-1,2], yi, c.pos[i,2])
                end

                if p1inside
                    # end existing segment
                    if !seg_now
235
236
237
                        # contour end on the first segment
                        t_start = 0
                        seglen_sofar = 0
238
239
240
241
242
243
244
                    end
                    seglen_sofar += dist(c.pos[i-1, :], p_i)
                    push!(segcontours, cid)
                    push!(seglen, seglen_sofar)
                    push!(segoffset, (t_i + t_start)/2)
                    seglen_sofar = 0
                    seg_now = false
245
                else
246
247
248
249
                    # start new contour
                    t_start = t_i
                    seglen_sofar = dist(p_i, c.pos[i, :])
                    seg_now = true
250
                end
251
                continue
252

253
254
255
256
257
            elseif sum([cross_side1, cross_side2, cross_side3, cross_side4]) >= 2
                # intersects twice
                p_is = []
                t_is = []
                if cross_side1
258
259
260
261
262
                    p = interpolate(c.pos[i-1,:], c.pos[i,:], voxx1, 1)
                    if !isnan(p[1])
                        push!(p_is, p)
                        push!(t_is, interpolate(c.time[i-1], c.time[i], c.pos[i-1,1], voxx1, c.pos[i,1]))
                    end
263
264
                end
                if cross_side2
265
266
267
268
269
                    p = interpolate(c.pos[i-1,:], c.pos[i,:], voxy1, 2)
                    if !isnan(p[1])
                        push!(p_is,p)
                        push!(t_is, interpolate(c.time[i-1], c.time[i], c.pos[i-1,2], voxy1, c.pos[i,2]))
                    end
270
271
                end
                if cross_side3
272
273
274
275
276
                    p = interpolate(c.pos[i-1,:], c.pos[i,:], voxx2, 1)
                    if !isnan(p[1])
                        push!(p_is,p)
                        push!(t_is, interpolate(c.time[i-1], c.time[i], c.pos[i-1,1], voxx2, c.pos[i,1]))
                    end
277
278
                end
                if cross_side4
279
280
281
282
283
                    p = interpolate(c.pos[i-1,:], c.pos[i,:], voxy2, 2)
                    if !isnan(p[1])
                        push!(p_is, p)
                        push!(t_is, interpolate(c.time[i-1], c.time[i], c.pos[i-1,2], voxy2, c.pos[i,2]))
                    end
284
                end
285

286
287
288
289
                if seg_now
                    print("Something's wrong")
                end

290
291
292
293
294
295
296
297
                if length(p_is) >= 2
                    push!(segoffset, mean(t_is))
                    push!(segcontours, cid)
                    if length(p_is) == 2
                        push!(seglen, dist(p_is[1], p_is[2]))
                    else
                        push!(seglen, dist(p_is[1], p_is[3]))
                    end
298
                else
299
300
301
302
303
304
305
306
                    p1inside = c.pos[i-1, 1] <= voxx1 && c.pos[i-1, 1] >= voxx2 &&
                            c.pos[i-1, 2] >= voxy2 && c.pos[i-1, 2] <= voxy1
                    p = p1inside ? c.pos[i-1,:] : c.pos[i,:]
                    t = p1inside ? c.time[i-1] : c.time[i]

                    push!(segcontours, cid)
                    push!(segoffset, (t + t_is[1])/2)
                    push!(seglen, dist(p_is[1], p))
307
                end
308
309
310
            end
        end

311
312
313
314
315
316
317
318
319
320
321
        # if contour ends inside the voxel
        if seg_now
            # end segment
            push!(segcontours, cid)
            push!(seglen, seglen_sofar)
            push!(segoffset, (t_start + last(c.time))/2)
            seglen_sofar = 0
            t_start = 0
            seg_now = false
        end

322
323
        # for those contours find exact segments
    end
324
    return voxmap(seglen, segoffset, segcontours)
325
326
end

327

328
329
330
function voxdata(fname::String, cdata::contourdata)
    voxels = DataFrames.DataFrame(CSV.File(fname))
    w = dist(Vector(voxels[1, ["x","y","z"]]), Vector(voxels[2, ["x","y","z"]]))
Jayant Khatkar's avatar
Jayant Khatkar committed
331
    println("Assumed width ", w)
332
333
334
335
336
337
338
339
340
    vpos = [[v.x, v.y, v.z] for v in eachrow(voxels)]
    voxms = [voxmap(v, w, cdata) for v in vpos]
    below = indexin([v - [0,0,cdata.layer_height] for v in vpos], vpos)
    replace!(below, nothing=>0)
    return voxdata(voxels, voxms, below, w)
end


function random_rollout(cdata::contourdata)
341
    done_contours = Set{Int}()
342
343
    avail_contours = Set(cdata.layers[1])
    todo_contours = Set(1:length(cdata.contours))
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
    rollout = Vector{Int}()

    while length(avail_contours) > 0
        c = rand(avail_contours)
        push!(rollout, c)

        # remove selected contour from todo and avail, add to done
        delete!(avail_contours, c)
        delete!(todo_contours, c)
        push!(done_contours, c)

        # update available contours
        for i in todo_contours
            if i in avail_contours
                continue
359
            elseif length(inneighbors(cdata.G, i)) == 0
360
361
362
363
364
                push!(avail_contours, i)
                continue
            end

            add = true
365
            for j in inneighbors(cdata.G, i)
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
                if !(j in done_contours)
                    add = false
                    break
                end
            end

            if add
                push!(avail_contours, i)
            end
        end
    end

    return rollout
end


382
function valid_swap(rollout::Vector{Int}, i::Int, j::Int, cdata::contourdata)
383
384
385
    # would swapping indices i and j in rollout result in another valid rollout?
    # NOTE THIS FUNCTION DOESNT WORK
    # IT ONLY CHECKS DEPENDENCIES TO A DEPTH OF 1
386
    # TODO, leave for now, use check_validity to double check at the end
387
388
389
390
391
392
393
394
395

    if i>j
        i,j = j,i
    elseif i==j
        return true
    end

    c1 = rollout[i]
    c2 = rollout[j]
396
    c2_dependson = inneighbors(cdata.G, c2)
397
398
399
400
401

    if c1 in c2_dependson
        return false
    end

402
    c1_dependents = outneighbors(cdata.G, c1)
403
404
405
406
407
408
409
410
411
412
413
414
    c_between = rollout[i+1:j-1]

    for c in c_between
        if c in c1_dependents || c in c2_dependson
            return false
        end
    end

    return true
end


415
function check_validity(rollout::Vector{Int}, cdata::contourdata)
416
417
418
419
    # make sure a given rollout is valid
    done_contours = Set{Int}()

    for c in rollout
420
        c_dependson = inneighbors(cdata.G, c)
421
422
423
424
425
426
427
428
429
430
431

        if !issubset(c_dependson, done_contours)
            return false
        end

        push!(done_contours, c)
    end
    return true
end


432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
function test_voxmap()
    # create vox
    vox = [0,0,0.5]
    vox_d = 2
    pos1 = [[0.5, -0.5] ones(2)*0.5 ones(2)]
    time1 = [0,1]
    pos2 = [[1.5, 0.5, -0.5, -1.5] ones(4)*0.5 ones(4)]
    time2 = Vector(0:3)
    pos3 = [[-0.5, -0.5] [2, -2] ones(2)]
    time3 = [0, 2.5]
    pos4 = [[0.5, 2.5] [-1.5, -0.5] ones(2)]
    time4 = [0,1]
    pos5 = [[-2,2] [-2,2] ones(2)]
    time5 = [0,1]
    contour1 = contour(pos1, time1)
    contour2 = contour(pos2,time2)
    contour3 = contour(pos3,time3)
    contour4 = contour(pos4,time4)
    contour5 = contour(pos5,time5)

    contours = [contour1, contour2, contour3, contour4, contour5]
453
454
    cdata = contourdata(contours, 1, 1)
    vm = voxmap(vox, vox_d, cdata)
455
    return vm
456
457
458
end


459
function rollout2time(rollout::Vector{Int}, cdata::contourdata)
460
    # start time of each contour, assuming no travel time
461
    return cumsum([cdata.contours[c].time[end] for c in rollout])
462
463
end

464
465
466
467
# Temperature function
T0 = 215 # extrusion temp
Tc = 25 # room temp
Tcutoff = 100 # temperature above which strain isn't happening
468
k = 0.02 #value unknown
469
470
471
472
473
Temp(t::Number) = Tc + (T0-Tc)*^(-k*t)
# see shape of temp function
#x = 1:100
#y = Temp.(x)
#plot(x,y)
474

475
function calc_cost(rollout::Vector{Int}, cdata::contourdata, vd::voxdata)
476
477

    # go from rollout to timestart for each contour
478
    timestart = rollout2time(rollout, cdata)
479
480

    # calculate time at each voxel
481
482
483
    voxtimes = [sum(v.seglen.*(v.segoffset + timestart[v.segcontours]))/sum(v.seglen) for v in vd.maps]
    println("Empty voxels: ", sum(isnan.(voxtimes)))
    #replace!(voxtimes, NaN=>0)
484
485

    # calculate temp difference from voxel below it
486
487
488
    considered_voxels = (1:length(vd.below))[(below.!=0) .& (.!isnan.(voxtimes))] # cannot calculate cost is no voxel underneath
    considered_voxels = considered_voxels[.!isnan.(voxtimes[below[considered_voxels]])]
    Δt = voxtimes[considered_voxels] - voxtimes[below[considered_voxels]]
489
    ΔT = Tcutoff .- Temp.(Δt)
490
491
492
493
494
495
496
497
498

    # calculate stresses at each voxel

    # calculate cost func at each voxel

    # sum over the voxels
end


499
function construct_cost(cdata::contourdata)
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
    a = 1
    b = :($a + 5) # using $ 'interpolates' literal expression into the 'quoted' expression
    c = :(5*5 + a)

    d = :($b + $c) #interpolate other expressions to form larger expressions

    ex1 = :(i*2) # construct this according to voxels and contours
    ex2 = quote
        function cost_f(i::Int)
            return $ex1
        end
    end
    return eval(ex2) # return the contructed function
end

Jayant Khatkar's avatar
Jayant Khatkar committed
515
516
517
518
519
520
521
522
function clean_contour(c::contour)
    # remove first element of array if second element is the same
    while c.pos[1,:] == c.pos[2,:]
        c.pos = c.pos[2:end, :]
    end
    return c
end

523

Jayant Khatkar's avatar
Jayant Khatkar committed
524
525
obj = "/Users/jayant/phd/tempaware/" * "M1"
contours = clean_contour.(contour.(JSON.parse(open(obj * "contours.json"))))
526
cdata = contourdata(contours, 5, 5) # contour data
Jayant Khatkar's avatar
Jayant Khatkar committed
527
528
529
vd = voxdata(obj * "_voxels.csv", cdata) # TODO Need to debug
@benchmark rl = random_rollout(cdata) # 20/second
@benchmark valid_swap(rl, rand(1:length(contours)), rand(1:length(contours)), cdata) # 1mil/second
530
rl = random_rollout(cdata)