nx_uv_dual_partition_candidate_t280.nx source
↩ module page · 80 lines · 5349 B
1// nx_uv_dual_partition_candidate_t280.nx -- Partitions a chart's dual face graph into two connected components based on shortest-path distances.
2import "nx_uv_closed_cut_candidate_t280.nx"
3func uvd_boundary(m:*i64,t:i64,c:i64)->i64{
4 var k:i64=0;while k<3{let a:i64=uv_ti(m,t,k);let b:i64=uv_ti(m,t,(k+1)%3)
5 if uv_is_seam(m,a,b)!=0{return 1}
6 let e:i64=uvi_edge_find(m,a,b);if e<0{return 0-1}
7 let o:i64=m[UV_O_ETAB]+e*UV_EREC;var nb:i64=m[o+UV_ED_T0]-1;if nb==t{nb=m[o+UV_ED_T1]-1}
8 if nb<0{return 1};if uv_chart_of_tri(m,nb)!=c{return 1};k=k+1
9 };return 0
10}
11func uvd_opposite(m:*i64,t:i64,a:i64,b:i64)->i64{
12 var k:i64=0;while k<3{let v:i64=uv_ti(m,t,k);if v!=a{if v!=b{return v}};k=k+1};return 0-1
13}
14// Two connected shortest-path cells in a chart's dual face graph. Edge
15// weights are three times centroid distance, exactly the opposite-vertex
16// distance for two triangles sharing an edge (all in source Q12 length).
17// No anatomical label or source geometry is rewritten.
18func uvd_partition(m:*i64,c:i64,target:*i64,receipt:*i64)->*i64{
19 if receipt==(0 as *i64){return 0 as *i64};receipt[0]=0
20 if m==(0 as *i64){return 0 as *i64};if target==(0 as *i64){return 0 as *i64}
21 if uv_stage(m)<UV_ST_CHARTS{return 0 as *i64};if uv_stage(target)!=UV_ST_NEW{return 0 as *i64}
22 if c<0{return 0 as *i64};if c>=uv_chart_count(m){return 0 as *i64}
23 if target[UV_H_NV]!=m[UV_H_NV]{return 0 as *i64};if target[UV_H_NT]!=m[UV_H_NT]{return 0 as *i64}
24 var v:i64=0;while v<m[UV_H_NV]{if uv_vx(m,v)!=uv_vx(target,v){return 0 as *i64};if uv_vy(m,v)!=uv_vy(target,v){return 0 as *i64};if uv_vz(m,v)!=uv_vz(target,v){return 0 as *i64};v=v+1}
25 var t:i64=0;while t<m[UV_H_NT]{var k:i64=0;while k<3{if uv_ti(m,t,k)!=uv_ti(target,t,k){return 0 as *i64};k=k+1};t=t+1}
26 if uv_seam_count(target)!=uv_seam_count(m){return 0 as *i64}
27 var slot:i64=0;while slot<m[UV_H_SCAP]{let so:i64=m[UV_O_STAB]+slot*UV_SREC;if m[so+UV_SM_USED]!=0{if uv_is_seam(target,m[so+UV_SM_LO],m[so+UV_SM_HI])==0{return 0 as *i64}};slot=slot+1}
28 let p0:i64=m[m[UV_O_CSTART]+c];let n:i64=m[m[UV_O_CSTART]+c+1]-p0;if n<2{return 0 as *i64}
29 if n>(NCP_MAX/UV_I64-m[UV_H_NT])/3{return 0 as *i64}
30 let bytes:i64=(m[UV_H_NT]+n*3)*UV_I64
31 let work:*i64=sys_mmap_try(bytes) as *i64;if (work as i64)<=0{return 0 as *i64}
32 let da:*i64=((work as i64)+m[UV_H_NT]*UV_I64) as *i64
33 let db:*i64=((da as i64)+n*UV_I64) as *i64
34 let pred:*i64=((db as i64)+n*UV_I64) as *i64
35 var i:i64=0;while i<n{work[m[m[UV_O_CORDER]+p0+i]]=i;i=i+1}
36 let g:*GraphAdj=nx_graphalg_alloc(n,UV_TRI);var valid:i64=1;i=0
37 while i<n{t=m[m[UV_O_CORDER]+p0+i];var k:i64=0;while k<3{
38 let a:i64=uv_ti(m,t,k);let b:i64=uv_ti(m,t,(k+1)%3)
39 if uv_is_seam(m,a,b)==0{
40 let e:i64=uvi_edge_find(m,a,b);if e<0{valid=0;break}
41 let eo:i64=m[UV_O_ETAB]+e*UV_EREC;var nb:i64=m[eo+UV_ED_T0]-1;if nb==t{nb=m[eo+UV_ED_T1]-1}
42 if nb>=0{if uv_chart_of_tri(m,nb)==c{let j:i64=work[nb];if i<j{
43 let va:i64=uvd_opposite(m,t,a,b);let vb:i64=uvd_opposite(m,nb,a,b)
44 if va<0{valid=0;break};if vb<0{valid=0;break};let w:i64=uvi_len_q(m,va,vb)
45 if w<=0{valid=0;break};if w>(NX_GRAPHALG_INF-1)/n{valid=0;break}
46 if nx_graphalg_add_undirected_edge(g,i,j,w)!=0{valid=0;break}
47 }}}
48 };k=k+1
49 };if valid==0{break};i=i+1}
50 var sa:i64=0-1;var sb:i64=0-1
51 if valid==1{if nx_graphalg_dijkstra(g,0,da,pred)!=0{valid=0}}
52 if valid==1{i=0;while i<n{if da[i]>=NX_GRAPHALG_INF{valid=0;break};let border:i64=uvd_boundary(m,m[m[UV_O_CORDER]+p0+i],c);if border<0{valid=0;break};if border==1{if sa<0{sa=i}else{if da[i]>da[sa]{sa=i}}};i=i+1};if sa<0{valid=0}}
53 if valid==1{if nx_graphalg_dijkstra(g,sa,da,pred)!=0{valid=0}}
54 if valid==1{i=0;while i<n{let border:i64=uvd_boundary(m,m[m[UV_O_CORDER]+p0+i],c);if border<0{valid=0;break};if border==1{if sb<0{sb=i}else{if da[i]>da[sb]{sb=i}}};i=i+1};if sb<0{valid=0};if sb==sa{valid=0}}
55 if valid==1{if nx_graphalg_dijkstra(g,sb,db,pred)!=0{valid=0}}
56 var count:i64=0;var groupA:i64=0;var groupB:i64=0
57 if valid==1{i=0;while i<n{pred[i]=0;if db[i]<da[i]{pred[i]=1;groupB=groupB+1}else{groupA=groupA+1};i=i+1}
58 i=0;while i<n{var j:i64=0;while j<g.adj_size[i]{let other:i64=g.adj_to[i*g.max_edges+j];if i<other{if pred[i]!=pred[other]{count=count+1}};j=j+1};i=i+1}
59 if count<1{valid=0}
60 }
61 var out:*i64=0 as *i64
62 if valid==1{
63 out=sys_mmap_try((1+count*2)*UV_I64) as *i64
64 if (out as i64)<=0{out=0 as *i64;valid=0}else{
65 out[0]=count;var written:i64=0;i=0
66 while i<n{t=m[m[UV_O_CORDER]+p0+i];var k:i64=0;while k<3{
67 let a:i64=uv_ti(m,t,k);let b:i64=uv_ti(m,t,(k+1)%3)
68 if uv_is_seam(m,a,b)==0{let e:i64=uvi_edge_find(m,a,b);let eo:i64=m[UV_O_ETAB]+e*UV_EREC;var nb:i64=m[eo+UV_ED_T0]-1;if nb==t{nb=m[eo+UV_ED_T1]-1}
69 if nb>=0{if uv_chart_of_tri(m,nb)==c{let j:i64=work[nb];if i<j{if pred[i]!=pred[j]{
70 if written>=count{valid=0;break};out[1+written*2]=a;out[2+written*2]=b;written=written+1
71 }}}}
72 };k=k+1
73 };if valid==0{break};i=i+1}
74 if written!=count{valid=0}
75 if valid==1{i=0;while i<count{if uv_seam_set(target,out[1+i*2],out[2+i*2])!=UV_OK{valid=0;break};i=i+1}}
76 if valid==0{sys_munmap_direct(out as *u8,(1+count*2)*UV_I64);out=0 as *i64}else{receipt[0]=1+count*2;receipt[1]=m[m[UV_O_CORDER]+p0+sa];receipt[2]=m[m[UV_O_CORDER]+p0+sb];receipt[3]=groupA;receipt[4]=groupB;receipt[5]=da[sb]}
77 }
78 }
79 uct_graph_free(g);sys_munmap_direct(work as *u8,bytes);return out
80}