"""Conservative exact-rational certificate on the stored binary-float tet domain. No approximate predicate can turn UNKNOWN into acceptance. Complexity and CPU limits return UNKNOWN. This certifies selected subpatches, not CAD wall truth. """ from fractions import Fraction as F from itertools import combinations from math import gcd,lcm import time class Unknown(RuntimeError):pass class Work: def __init__(self,operations=70000,cpu_seconds=300): self.operations=0;self.limit=operations;self.start=time.process_time();self.cpu_limit=cpu_seconds def tick(self): self.operations+=1 if self.operations>self.limit or time.process_time()-self.start>self.cpu_limit:raise Unknown('exact predicate complexity/CPU limit') def point(p):return tuple(F.from_float(float(v)) for v in p) def sub(a,b):return tuple(x-y for x,y in zip(a,b)) def dot(a,b):return sum(x*y for x,y in zip(a,b)) def cross(a,b):return (a[1]*b[2]-a[2]*b[1],a[2]*b[0]-a[0]*b[2],a[0]*b[1]-a[1]*b[0]) def det(a,b,c):return dot(a,cross(b,c)) def primitive(values): den=lcm(*(v.denominator for v in values));nums=[int(v*den) for v in values] div=gcd(*map(abs,nums)) if div==0:raise Unknown('zero plane') return tuple(v//div for v in nums) def tetra_planes(vertices): x=tuple(vertices);planes=[] if det(sub(x[1],x[0]),sub(x[2],x[0]),sub(x[3],x[0]))==0:raise Unknown('degenerate tet') for omitted in range(4): face=[x[i] for i in range(4) if i!=omitted];n=cross(sub(face[1],face[0]),sub(face[2],face[0]));d=-dot(n,face[0]) if dot(n,x[omitted])+d>0:n=tuple(-v for v in n);d=-d planes.append(primitive((*n,d))) return tuple(planes) def evalplane(plane,p):return dot(plane[:3],p)+plane[3] def vertices(planes,work): planes=tuple(dict.fromkeys(planes)) if len(planes)>24:raise Unknown('too many clipping planes') out=set() for a,b,c in combinations(planes,3): work.tick();den=det(a[:3],b[:3],c[:3]) if den==0:continue bc=cross(b[:3],c[:3]);ca=cross(c[:3],a[:3]);ab=cross(a[:3],b[:3]) p=tuple(F(-a[3]*bc[i]-b[3]*ca[i]-c[3]*ab[i],den) for i in range(3)) if all(evalplane(h,p)<=0 for h in planes):out.add(p) return tuple(sorted(out)) def poly(planes,work): h=tuple(dict.fromkeys(planes));return h,vertices(h,work) def hull2(items,axes): ordered=sorted(items,key=lambda p:(p[axes[0]],p[axes[1]])) def turn(a,b,c):return (b[axes[0]]-a[axes[0]])*(c[axes[1]]-a[axes[1]])-(b[axes[1]]-a[axes[1]])*(c[axes[0]]-a[axes[0]]) lower=[];upper=[] for p in ordered: while len(lower)>1 and turn(lower[-2],lower[-1],p)<=0:lower.pop() lower.append(p) for p in reversed(ordered): while len(upper)>1 and turn(upper[-2],upper[-1],p)<=0:upper.pop() upper.append(p) return lower[:-1]+upper[:-1] def volume(p): planes,verts=p if len(verts)<4:return F(0) directions=[sub(v,verts[0]) for v in verts[1:]] first=next((v for v in directions if any(v)),None) if first is None:return F(0) normal=next((cross(first,v) for v in directions if any(cross(first,v))),None) if normal is None or all(dot(normal,v)==0 for v in directions):return F(0) total=F(0);seen=set() for plane in planes: face=tuple(v for v in verts if evalplane(plane,v)==0) if len(face)<3 or frozenset(face) in seen:continue seen.add(frozenset(face));axis=max(range(3),key=lambda i:abs(plane[i]));axes=[i for i in range(3) if i!=axis] boundary=hull2(face,axes) if plane[axis]*(1 if axis!=1 else -1)<0:boundary.reverse() for j in range(1,len(boundary)-1):total+=det(boundary[0],boundary[j],boundary[j+1])/6 if total<0:raise Unknown('oriented volume inconsistency') return total def clip(p,plane,work): h,v=p if not v:return p vals=[evalplane(plane,x) for x in v] if max(vals)<=0:return p if min(vals)>0:return (h+(plane,),()) return poly(h+(plane,),work) def outside(p,solid_planes,work): remaining=p;pieces=[] for h in solid_planes: if not remaining[1]:break fragment=clip(remaining,tuple(-v for v in h),work) if volume(fragment)>0:pieces.append(fragment) remaining=clip(remaining,h,work) return pieces def in_common(p,shared): if not shared:return False if len(shared)==1:return p==shared[0] a=shared[0];b=sub(shared[1],a);v=sub(p,a) if len(shared)==2: k=next((i for i in range(3) if b[i]!=0),None) if k is None:return p==a t=v[k]/b[k];return 0<=t<=1 and all(v[i]==t*b[i] for i in range(3)) c=sub(shared[2],a) for i,j in combinations(range(3),2): d=b[i]*c[j]-b[j]*c[i] if d: u=(v[i]*c[j]-v[j]*c[i])/d;w=(b[i]*v[j]-b[j]*v[i])/d return u>=0 and w>=0 and u+w<=1 and all(v[k]==u*b[k]+w*c[k] for k in range(3)) raise Unknown('degenerate shared reference face') PRISM=((0,1,2,5),(0,4,1,5),(0,3,4,5)) def certify(points,cavity_tets,work=None): work=work or Work();x=tuple(point(p) for p in points) reference_order=(0,1,2,3,4,5) if len(x)!=6 or len(set(x))!=6:return dict(status='REJECT',reason='non-distinct prism vertices') signs=[det(sub(x[t[1]],x[t[0]]),sub(x[t[2]],x[t[0]]),sub(x[t[3]],x[t[0]])) for t in PRISM] if all(v<0 for v in signs): reference_order=(0,2,1,3,5,4) x=tuple(x[i] for i in (0,2,1,3,5,4));signs=[det(sub(x[t[1]],x[t[0]]),sub(x[t[2]],x[t[0]]),sub(x[t[3]],x[t[0]])) for t in PRISM] if any(v<=0 for v in signs):return dict(status='REJECT',reason='folded or degenerate product mapping') polys=[(tetra_planes([x[i] for i in t]),tuple(x[i] for i in t)) for t in PRISM] for i,j in combinations(range(3),2): intersection=vertices(polys[i][0]+polys[j][0],work) shared=[x[k] for k in sorted(set(PRISM[i]) & set(PRISM[j]))] if any(not in_common(p,shared) for p in intersection):return dict(status='REJECT',reason='nonlocal image self intersection') cavity=[] for t in cavity_tets: work.tick();cavity.append(tetra_planes(tuple(point(p) for p in t))) for p in polys: uncovered=[p] for planes in cavity: work.tick() uncovered=[q for prior in uncovered for q in outside(prior,planes,work)] if len(uncovered)>256:raise Unknown('uncovered polytope count cap') if not uncovered:break if uncovered:return dict(status='REJECT',reason='positive volume outside original cavity union',uncovered_volume=float(sum(volume(p) for p in uncovered))) v=sum(signs)/6 return dict(status='CERTIFIED',volume=float(v),volume_fraction_exact=[str(v.numerator),str(v.denominator)], operations=work.operations,verification='exact rational predicates for stored binary-float coordinates',tetrahedra=3, reference_vertex_order=list(reference_order))