nx_uv_cached_solver_candidate_t280.nx source
↩ module page · 159 lines · 7833 B
1// nx_uv_cached_solver_candidate_t280.nx -- Caches UV solve data per model to improve performance and reduce recomputation.
2import "nx_nxa_corner_prepare_candidate_t280.nx"
3// Candidate extension to the existing UV solver. One active solve context per model:
4// the canonical solver's list/accumulator arrays are shared scratch.
5struct UvCachedSolve{
6 m:*i64,c:i64,n:i64,pa:i64,pb:i64,cap:i64,used:i64,maxmove:i64,result:i64,
7 weights:*i64,weightBytes:i64,triangles:i64,triangleVisits:i64,cotangentCalls:i64,
8 pinsUs:i64,initialUs:i64,weightsUs:i64,solveUs:i64,clock:*i64
9}
10const UVC_YIELDED:i64=1
11func uvc_now(s:*UvCachedSolve)->i64{
12 if s.clock==(0 as *i64){return 0-1}
13 if sys_clock_gettime_mono(s.clock)!=0{return 0-1}
14 return s.clock[0]*1000000+s.clock[1]/1000
15}
16func uvc_elapsed(a:i64,b:i64)->i64{if a<0{return 0-1};if b<a{return 0-1};return b-a}
17func uvc_begin(m:*i64,c:i64)->*UvCachedSolve{
18 if m==(0 as *i64){return 0 as *UvCachedSolve}
19 if uv_stage(m)<UV_ST_CHARTS{return 0 as *UvCachedSolve}
20 if c<0{return 0 as *UvCachedSolve};if c>=uv_chart_count(m){return 0 as *UvCachedSolve}
21 let s:*UvCachedSolve=sys_mmap_try(__size_of(UvCachedSolve)) as *UvCachedSolve
22 if (s as i64)<=0{return 0 as *UvCachedSolve}
23 s.m=m;s.c=c;s.result=UV_E_NOTRUN
24 s.clock=sys_mmap_try(2*UV_I64) as *i64;if (s.clock as i64)<=0{s.clock=0 as *i64}
25 let pins:*i64=sys_mmap_try(UV_MIN_PINS*UV_I64) as *i64
26 if (pins as i64)<=0{s.result=UV_E_ARGS;return s}
27 let a:i64=uvc_now(s);let count:i64=uv_pins_for(m,c,pins);s.pinsUs=uvc_elapsed(a,uvc_now(s))
28 s.pa=pins[0];s.pb=pins[1];sys_munmap_direct(pins as *u8,UV_MIN_PINS*UV_I64)
29 if count<UV_MIN_PINS{s.result=UV_E_NOPIN;return s}
30 s.n=uvi_chart_classes(m,c)
31 s.cap=s.n*UV_ITER_PER_UVV;if s.cap<UV_ITER_MIN{s.cap=UV_ITER_MIN}
32 let b:i64=uvc_now(s);let rc:i64=uvi_initial(m,c,s.n,s.pa,s.pb);s.initialUs=uvc_elapsed(b,uvc_now(s))
33 if rc!=UV_OK{s.result=rc;return s}
34 let p0:i64=m[m[UV_O_CSTART]+c];let p1:i64=m[m[UV_O_CSTART]+c+1]
35 s.triangles=p1-p0;s.weightBytes=s.triangles*UV_TRI*UV_I64
36 s.weights=sys_mmap_try(s.weightBytes) as *i64
37 if (s.weights as i64)<=0{s.weights=0 as *i64;s.result=UV_E_ARGS;return s}
38 let d:i64=uvc_now(s);var p:i64=p0
39 while p<p1{
40 let t:i64=m[m[UV_O_CORDER]+p]
41 let ci:i64=m[m[UV_O_UVF]+t*UV_TRI];let cj:i64=m[m[UV_O_UVF]+t*UV_TRI+1];let ck:i64=m[m[UV_O_UVF]+t*UV_TRI+2]
42 let vi:i64=m[m[UV_O_UVSRC]+ci];let vj:i64=m[m[UV_O_UVSRC]+cj];let vk:i64=m[m[UV_O_UVSRC]+ck]
43 s.weights[(p-p0)*UV_TRI]=uvi_cotq(m,vi,vj,vk)
44 s.weights[(p-p0)*UV_TRI+1]=uvi_cotq(m,vj,vk,vi)
45 s.weights[(p-p0)*UV_TRI+2]=uvi_cotq(m,vk,vi,vj)
46 p=p+1
47 }
48 s.cotangentCalls=s.triangles*UV_TRI;s.weightsUs=uvc_elapsed(d,uvc_now(s));return s
49}
50func uvc_free(s:*UvCachedSolve)->i64{
51 if s==(0 as *UvCachedSolve){return 0}
52 if s.weights!=(0 as *i64){sys_munmap_direct(s.weights as *u8,s.weightBytes)}
53 if s.clock!=(0 as *i64){sys_munmap_direct(s.clock as *u8,2*UV_I64)}
54 return sys_munmap_direct(s as *u8,__size_of(UvCachedSolve))
55}
56func uvc_step(s:*UvCachedSolve,budget:i64)->i64{
57 if s==(0 as *UvCachedSolve){return UV_E_ARGS};if budget<1{return UV_E_ARGS}
58 if s.result!=UV_E_NOTRUN{return s.result}
59 let m:*i64=s.m;let c:i64=s.c;let n:i64=s.n;let pa:i64=s.pa;let pb:i64=s.pb
60 let started:i64=uvc_now(s);let before:i64=s.used
61 let list: i64 = m[UV_O_LIST]
62 let uvf: i64 = m[UV_O_UVF]
63 let uvsrc: i64 = m[UV_O_UVSRC]
64 let wu: i64 = m[UV_O_WU]
65 let wv: i64 = m[UV_O_WV]
66 let au: i64 = m[UV_O_ACCU]
67 let av: i64 = m[UV_O_ACCV]
68 let aw: i64 = m[UV_O_ACCW]
69 let aau: i64 = m[UV_O_ACCAU]
70 let aav: i64 = m[UV_O_ACCAV]
71 let p0: i64 = m[m[UV_O_CSTART] + c]
72 let p1: i64 = m[m[UV_O_CSTART] + c + 1]
73 let cap:i64=s.cap
74 var allowance:i64=budget;if allowance>cap-s.used{allowance=cap-s.used}
75 var it: i64 = 0
76 var used: i64 = s.used
77 var done: i64 = 0
78 var maxmove: i64 = s.maxmove
79 // THE LOOP CURSOR IS NOT THE ANSWER. Leaving early by writing the cap into the cursor would erase the
80 // very number this function has to report, so the sweep count is carried in a counter of its own and
81 // the cursor is free to be used as the exit sentinel.
82 while it < allowance {
83 if done == 0 {
84 var i: i64 = 0
85 while i < n {
86 let z: i64 = m[list + i]
87 m[au + z] = 0
88 m[av + z] = 0
89 m[aw + z] = 0
90 m[aau + z] = 0
91 m[aav + z] = 0
92 i = i + 1
93 }
94 var p: i64 = p0
95 while p < p1 {
96 let t: i64 = m[m[UV_O_CORDER] + p]
97 let ci: i64 = m[uvf + t * UV_TRI + 0]
98 let cj: i64 = m[uvf + t * UV_TRI + 1]
99 let ck: i64 = m[uvf + t * UV_TRI + 2]
100 let vi: i64 = m[uvsrc + ci]
101 let vj: i64 = m[uvsrc + cj]
102 let vk: i64 = m[uvsrc + ck]
103 // weight on edge (i,j) is the cotangent at k, and so round the triangle
104 let wk:i64=s.weights[(p-p0)*UV_TRI+0]
105 let wi:i64=s.weights[(p-p0)*UV_TRI+1]
106 let wj:i64=s.weights[(p-p0)*UV_TRI+2]
107 m[aw + ci] = m[aw + ci] + wk + wj
108 m[aw + cj] = m[aw + cj] + wk + wi
109 m[aw + ck] = m[aw + ck] + wi + wj
110 m[au + ci] = m[au + ci] + wk * m[wu + cj] + wj * m[wu + ck]
111 m[au + cj] = m[au + cj] + wk * m[wu + ci] + wi * m[wu + ck]
112 m[au + ck] = m[au + ck] + wi * m[wu + cj] + wj * m[wu + ci]
113 m[av + ci] = m[av + ci] + wk * m[wv + cj] + wj * m[wv + ck]
114 m[av + cj] = m[av + cj] + wk * m[wv + ci] + wi * m[wv + ck]
115 m[av + ck] = m[av + ck] + wi * m[wv + cj] + wj * m[wv + ci]
116 // the area gradient: for corner i the neighbours in winding order are j (next) and k (prev)
117 m[aau + ci] = m[aau + ci] + m[wv + cj] - m[wv + ck]
118 m[aav + ci] = m[aav + ci] + m[wu + ck] - m[wu + cj]
119 m[aau + cj] = m[aau + cj] + m[wv + ck] - m[wv + ci]
120 m[aav + cj] = m[aav + cj] + m[wu + ci] - m[wu + ck]
121 m[aau + ck] = m[aau + ck] + m[wv + ci] - m[wv + cj]
122 m[aav + ck] = m[aav + ck] + m[wu + cj] - m[wu + ci]
123 p = p + 1
124 }
125 maxmove = 0
126 i = 0
127 while i < n {
128 let q: i64 = m[list + i]
129 var skip: i64 = 0
130 if q == pa { skip = 1 }
131 if q == pb { skip = 1 }
132 if m[aw + q] <= 0 { skip = 1; m[UV_H_SING] = m[UV_H_SING] + 1 }
133 if skip == 0 {
134 let den: i64 = m[aw + q]
135 let tu: i64 = (m[au + q] + UV_W_Q * m[aau + q]) / den
136 let tv: i64 = (m[av + q] + UV_W_Q * m[aav + q]) / den
137 let du: i64 = (tu - m[wu + q]) / UV_OMEGA_DEN
138 let dv: i64 = (tv - m[wv + q]) / UV_OMEGA_DEN
139 m[wu + q] = m[wu + q] + du
140 m[wv + q] = m[wv + q] + dv
141 let mvd: i64 = vm_abs(du) + vm_abs(dv)
142 if mvd > maxmove { maxmove = mvd }
143 }
144 i = i + 1
145 }
146 used = used + 1
147 if maxmove <= UV_CONV_EPS { done = 1; it = allowance }
148 }
149 it = it + 1
150 }
151 s.used=used;s.maxmove=maxmove;s.triangleVisits=s.triangleVisits+(used-before)*s.triangles
152 let elapsed:i64=uvc_elapsed(started,uvc_now(s))
153 if elapsed<0{s.solveUs=0-1}else{if s.solveUs>=0{s.solveUs=s.solveUs+elapsed}}
154 if done==0{if used<cap{return UVC_YIELDED}}
155 if used>m[UV_H_ITERS]{m[UV_H_ITERS]=used}
156 if maxmove>m[UV_H_MAXMOVE]{m[UV_H_MAXMOVE]=maxmove}
157 if done==0{m[UV_H_NOCONV]=m[UV_H_NOCONV]+1;s.result=UV_E_NOCONVERGE;return s.result}
158 s.result=UV_OK;return s.result
159}