Jerry
1912 lines
52 KiB
Markdown
1912 lines
52 KiB
Markdown
# STEP B-Rep 基础几何解释与残差递归算法规范
|
||
|
||
## 文档状态
|
||
|
||
- 状态：Proposed
|
||
- 规范版本：0.2
|
||
- 目标项目：SimpleCADAPI 2.x
|
||
- 输入：STEP 导入后得到的 B-Rep snapshot
|
||
- 输出：可重放的几何程序、有限解释证据、评分分量和最终验证指标
|
||
- v0.2 实体基础单元：Box、Cylinder、Cone、Sphere、Torus、RawBRep
|
||
- v0.2 组合操作：Union、Subtract
|
||
- v0.2 NURBS 能力：解析曲面约化、NURBS 面证据匹配、RawBRep 兜底；不从开放 NURBS 面猜测实体
|
||
- 非目标：证明原始 CAD feature history、识别 NACA 等领域参数族、保证全局最优、从 mesh 恢复解析 B-Rep
|
||
|
||
## 1. 摘要
|
||
|
||
STEP B-Rep 提供有限数量的 Face、Edge、Vertex、支撑几何及 topology，但通常不提供原始 primitive、Boolean 和 feature tree。本规范把逆向定义为以下有限搜索：
|
||
|
||
1. 将输入 B-Rep 转换为有限的面、边和邻接证据原子。
|
||
2. 只从输入中出现的有限几何事件枚举 Box、Cylinder、Cone、Sphere 和 Torus 候选。
|
||
3. 用显式谓词计算每个候选解释的证据原子 bitset。
|
||
4. 用版本化数值代价表达基础单元常见性和参数复杂度。
|
||
5. 对候选计算 `R+ = T - H` 和 `R- = H - T`，再递归解释每个 residual solid。
|
||
6. 用有硬预算的 Beam Search 枚举有限个完整程序。
|
||
7. 从头重放完整程序，并用 symmetric-difference、双向边界距离和法向误差判定几何等价。
|
||
8. 在验证通过且所有目标 SurfaceAtom 都有归属的程序中选择总代价最低者。
|
||
|
||
本文的规范性术语均映射到有限集合、公式、确定排序或返回 `OK | FAILED | TIMEOUT | BUDGET_EXHAUSTED` 的 kernel 调用。说明性文字不创建额外算法分支。
|
||
|
||
## 2. 输入、程序和总函数
|
||
|
||
### 2.1 输入
|
||
|
||
输入实体记为：
|
||
|
||
\[
|
||
T=(V,E,F,A)
|
||
\]
|
||
|
||
其中 `V`、`E`、`F` 和 topology relation 集合 `A` 均为有限集合。
|
||
|
||
### 2.2 输出程序
|
||
|
||
```text
|
||
Program := Box(parameters)
|
||
| Cylinder(parameters)
|
||
| Cone(parameters)
|
||
| Sphere(parameters)
|
||
| Torus(parameters)
|
||
| RawBRep(snapshot, byte_length, raw_stats)
|
||
| Union(Program, Program)
|
||
| Subtract(Program, Program)
|
||
```
|
||
|
||
内部搜索额外使用占位节点：
|
||
|
||
```text
|
||
Template := Program | Slot(slot_id)
|
||
```
|
||
|
||
完成程序不允许包含 `Slot`。
|
||
|
||
`RawBRep` 的参数不是 process-local kernel object。它是以下总函数的结果：
|
||
|
||
```text
|
||
SnapshotOf(shape, context) -> KernelResult[BRepSnapshot]
|
||
|
||
BRepSnapshot
|
||
profile = "simplecad-brep-snapshot-0.2"
|
||
bytes
|
||
sha256 = SHA256(bytes)
|
||
```
|
||
|
||
该 profile 的 encoder 必须保存重放 shape 所需的 Vertex、Edge curve、Face surface、trim、orientation、tolerance 和 topology relation，并对相同 evaluated B-Rep 和 profile 产生相同 bytes。若 backend 不提供该 profile，`SnapshotOf` 返回 `FAILED(UNSUPPORTED_SNAPSHOT_PROFILE)`。`RawBRepKey = snapshot.sha256`，`byte_length = len(snapshot.bytes)`；反序列化时必须重新计算 SHA-256 和 byte length 并相等。
|
||
|
||
`raw_stats` 是从 snapshot 解码结果重新枚举得到的 closed record：
|
||
|
||
```text
|
||
RawStats
|
||
analytic_face_count
|
||
nurbs_face_records # 每项含 NurbsCost 所需全部整数
|
||
edge_count
|
||
vertex_count
|
||
```
|
||
|
||
创建节点时从 `ResidualAnalysis` 复制；反序列化时从 snapshot 重算并要求相等。
|
||
|
||
### 2.3 Kernel 调用总类型
|
||
|
||
所有可能失败的 kernel 操作统一返回：
|
||
|
||
```text
|
||
KernelResult[T] :=
|
||
OK(value: T)
|
||
| FAILED(code: FailureCode)
|
||
| TIMEOUT
|
||
| BUDGET_EXHAUSTED
|
||
```
|
||
|
||
每次调用前执行：
|
||
|
||
```text
|
||
KernelContext.try_reserve(kind) :=
|
||
if monotonic_clock() >= deadline: TIMEOUT
|
||
elif total_calls + 1 > max_total_calls: BUDGET_EXHAUSTED
|
||
elif kind == BOOLEAN and boolean_calls + 1 > max_boolean_calls: BUDGET_EXHAUSTED
|
||
else increment counters and OK
|
||
```
|
||
|
||
所有 kernel API 都接收 `deadline`。分析阶段调用失败时，整个输入降级为 `RawBRep`；候选阶段调用失败时丢弃该候选；最终验证阶段调用失败时，该程序验证失败。
|
||
|
||
本规范的调用计数单位是本节列出的逻辑 kernel API 调用，不是 CAD kernel 内部函数调用次数。调用包装器必须在进入 backend 前执行一次 `try_reserve`。纯 CPU 循环每处理 1024 个元素检查一次 deadline；到期后返回 `TIMEOUT`。
|
||
|
||
特殊失败动作只有以下四类，后文不得隐式覆盖：
|
||
|
||
```text
|
||
initial/residual analysis failure -> 当前 task 只允许 RawExpansion
|
||
candidate construction/measurement failure -> 丢弃当前 candidate
|
||
residual generation failure -> 丢弃当前 candidate
|
||
validation failure -> 当前 program 的 ValidProgram = false
|
||
```
|
||
|
||
初始输入 analysis 失败时，只有 `SnapshotOf(target)` 成功才能返回 RawBRep；否则返回 `ANALYSIS_FAILED` 且 `program = null`。
|
||
|
||
### 2.4 空 shape
|
||
|
||
Boolean 结果类型为：
|
||
|
||
```text
|
||
BooleanShape := EMPTY | NONEMPTY(shape)
|
||
```
|
||
|
||
定义：
|
||
|
||
```text
|
||
volume(EMPTY) = 0
|
||
surface_area(EMPTY) = 0
|
||
components(EMPTY) = []
|
||
ValidSolid(EMPTY) = false
|
||
```
|
||
|
||
`EMPTY` 没有 bbox、Face、Edge 或 Vertex，不能成为 Program 叶节点。它只允许出现在 residual 和程序简化过程中。
|
||
|
||
### 2.5 几何程序执行
|
||
|
||
```text
|
||
Render(Box/Cylinder/Cone/Sphere/Torus) := kernel_construct_primitive(parameters)
|
||
Render(RawBRep(snapshot,byte_length,raw_stats)) := kernel_copy(snapshot)
|
||
Render(Union(A,B)) := kernel_regularized_union(Render(A), Render(B))
|
||
Render(Subtract(A,B)) := kernel_regularized_cut(Render(A), Render(B))
|
||
```
|
||
|
||
任一子调用不是 `OK` 时，父调用返回相同失败状态。
|
||
|
||
内部验证允许程序简化常量 `EMPTY`：
|
||
|
||
```text
|
||
Union(EMPTY,X) = X
|
||
Union(X,EMPTY) = X
|
||
Subtract(EMPTY,X) = EMPTY
|
||
Subtract(X,EMPTY) = X
|
||
```
|
||
|
||
完成输出程序执行常量折叠后不得含 `EMPTY`。
|
||
|
||
## 3. 完整配置
|
||
|
||
### 3.1 配置结构
|
||
|
||
```text
|
||
ReverseConfig
|
||
tolerance:
|
||
eps_linear
|
||
eps_angular
|
||
eps_radius
|
||
eps_surface
|
||
eps_normal
|
||
eps_volume
|
||
eps_area
|
||
eps_length
|
||
discretization:
|
||
face_deflection
|
||
face_angular_deflection
|
||
edge_step
|
||
nurbs_u_samples
|
||
nurbs_v_samples
|
||
max_mesh_area_relative_error
|
||
analysis:
|
||
max_analysis_entities
|
||
max_analysis_total_kernel_calls
|
||
max_event_records
|
||
analysis_timeout_seconds
|
||
candidates:
|
||
max_direction_clusters
|
||
max_extent_pairs_per_axis
|
||
max_box_frames
|
||
max_box_candidates_per_frame
|
||
max_candidates_per_type
|
||
boolean_prefilter_top_m
|
||
min_trigger_entities
|
||
min_support_coverage
|
||
max_candidate_attempts_per_task
|
||
max_candidate_kernel_calls_per_task
|
||
score:
|
||
reward_support
|
||
reward_boundary
|
||
reward_edge
|
||
reward_adjacency
|
||
penalty_leaf_cost
|
||
unmatched_support_penalty
|
||
unmatched_boundary_penalty
|
||
unmatched_edge_penalty
|
||
expansion_margin
|
||
cost:
|
||
type_cost_box
|
||
type_cost_cylinder
|
||
type_cost_cone
|
||
type_cost_sphere
|
||
type_cost_torus
|
||
type_cost_nurbs_face
|
||
type_cost_raw_brep
|
||
operation_cost_union
|
||
operation_cost_subtract
|
||
scalar_parameter_cost
|
||
search:
|
||
beam_width
|
||
max_task_depth
|
||
max_expanded_states
|
||
max_search_total_kernel_calls
|
||
max_search_boolean_calls
|
||
search_timeout_seconds
|
||
max_completed_programs_to_validate
|
||
max_pending_tasks_per_state
|
||
validation:
|
||
max_validation_total_kernel_calls
|
||
max_validation_boolean_calls
|
||
validation_timeout_seconds
|
||
```
|
||
|
||
### 3.2 默认容差
|
||
|
||
令输入 bbox 对角线为 `D`，STEP entity tolerance 最大值为 `t_step`：
|
||
|
||
\[
|
||
\epsilon_{linear}=\max(t_{step},10^{-9}D)
|
||
\]
|
||
|
||
\[
|
||
\epsilon_{surface}=2\epsilon_{linear}
|
||
\]
|
||
|
||
\[
|
||
\epsilon_{radius}=2\epsilon_{linear}
|
||
\]
|
||
|
||
\[
|
||
\epsilon_{angular}=10^{-7}
|
||
\]
|
||
|
||
\[
|
||
\epsilon_{normal}=10^{-6}
|
||
\]
|
||
|
||
\[
|
||
\epsilon_{volume}=\max(10^{-12}D^3,10\epsilon_{linear}^3)
|
||
\]
|
||
|
||
\[
|
||
\epsilon_{area}=\max(10^{-12}D^2,10\epsilon_{linear}^2)
|
||
\]
|
||
|
||
\[
|
||
\epsilon_{length}=\epsilon_{linear}
|
||
\]
|
||
|
||
角度单位为 radian，长度单位采用导入后统一的模型单位。
|
||
|
||
### 3.3 默认离散化与预算
|
||
|
||
```text
|
||
face_deflection = max(eps_surface / 2, 1e-6 * D)
|
||
face_angular_deflection = eps_normal / 2
|
||
edge_step = max(eps_length, 1e-4 * D)
|
||
nurbs_u_samples = 9
|
||
nurbs_v_samples = 9
|
||
max_mesh_area_relative_error = 1e-3
|
||
|
||
max_analysis_entities = 1000000
|
||
max_analysis_total_kernel_calls = 1000000
|
||
max_event_records = 1000000
|
||
analysis_timeout_seconds = 120
|
||
|
||
max_direction_clusters = 12
|
||
max_extent_pairs_per_axis = 8
|
||
max_box_frames = 64
|
||
max_box_candidates_per_frame = 16
|
||
max_candidates_per_type = 24
|
||
boolean_prefilter_top_m = 16
|
||
min_trigger_entities = 1
|
||
min_support_coverage = 0.01
|
||
max_candidate_attempts_per_task = 10000
|
||
max_candidate_kernel_calls_per_task = 100000
|
||
|
||
reward_support = 10.0
|
||
reward_boundary = 5.0
|
||
reward_edge = 2.0
|
||
reward_adjacency = 1.0
|
||
penalty_leaf_cost = 1.0
|
||
unmatched_support_penalty = 5.0
|
||
unmatched_boundary_penalty = 2.0
|
||
unmatched_edge_penalty = 1.0
|
||
expansion_margin = 2.0
|
||
|
||
type_cost_box = 1.0
|
||
type_cost_cylinder = 1.0
|
||
type_cost_cone = 1.5
|
||
type_cost_sphere = 1.5
|
||
type_cost_torus = 2.0
|
||
type_cost_nurbs_face = 4.0
|
||
type_cost_raw_brep = 8.0
|
||
operation_cost_union = 0.5
|
||
operation_cost_subtract = 0.5
|
||
scalar_parameter_cost = 0.05
|
||
|
||
beam_width = 8
|
||
max_task_depth = 10
|
||
max_expanded_states = 1000
|
||
max_search_total_kernel_calls = 1000000
|
||
max_search_boolean_calls = 500
|
||
search_timeout_seconds = 120
|
||
max_completed_programs_to_validate = 32
|
||
max_pending_tasks_per_state = 256
|
||
|
||
max_validation_total_kernel_calls = 1000000
|
||
max_validation_boolean_calls = 500
|
||
validation_timeout_seconds = 120
|
||
```
|
||
|
||
### 3.4 配置合法性
|
||
|
||
`ConfigValid(config)` 当且仅当：
|
||
|
||
- 所有浮点配置均为 finite。
|
||
- 所有 `eps_*`、`face_deflection`、`face_angular_deflection`、`edge_step` 和 timeout 严格大于 `0`。
|
||
- `0 < eps_angular < pi/2` 且 `0 < eps_normal < pi/2`。
|
||
- `nurbs_u_samples >= 3` 且 `nurbs_v_samples >= 3`。
|
||
- `0 <= max_mesh_area_relative_error < 1`。
|
||
- 所有 `max_*`、`beam_width` 和 `boolean_prefilter_top_m` 是有限正整数。
|
||
- `min_trigger_entities` 是有限非负整数。
|
||
- `0 <= min_support_coverage <= 1`。
|
||
- 所有 reward、penalty 和 cost 是 finite 且大于等于 `0`。
|
||
|
||
输入数值合法性：
|
||
|
||
```text
|
||
FiniteBRep(T) :=
|
||
every bbox coordinate, Vertex coordinate, curve parameter,
|
||
surface parameter, knot, weight and tolerance used by this algorithm is finite
|
||
and every radius used by an analytic record is > 0
|
||
and every direction consumed by normalize has norm > eps_linear
|
||
```
|
||
|
||
`t_step` 为所有 finite entity tolerance 的最大值；没有 entity tolerance 时取 `0`。`FiniteBRep == false` 时返回 `INVALID_INPUT`。
|
||
|
||
`ConfigValid == false` 时返回 `INVALID_CONFIG`，不调用 kernel。
|
||
|
||
## 4. 量化与确定顺序
|
||
|
||
### 4.1 量化
|
||
|
||
定义半数向正无穷舍入：
|
||
|
||
\[
|
||
Q(x,\epsilon)=\lfloor x/\epsilon+1/2\rfloor
|
||
\]
|
||
|
||
\[
|
||
Q_3(p,\epsilon)=(Q(p_x,\epsilon),Q(p_y,\epsilon),Q(p_z,\epsilon))
|
||
\]
|
||
|
||
单位方向 `d` 的规范符号：找到绝对值最大的分量；多个分量同大时按 `x,y,z` 选择第一个；若该分量小于 `0`，令 `d := -d`。
|
||
|
||
\[
|
||
Q_d(d)=Q_3(d,\sin(\epsilon_{angular}))
|
||
\]
|
||
|
||
### 4.2 基本方向谓词
|
||
|
||
定义有向夹角：
|
||
|
||
\[
|
||
angle(a,b)=acos(clamp(dot(a/\|a\|,b/\|b\|),-1,1))
|
||
\]
|
||
|
||
只有 `norm(a) > eps_linear` 且 `norm(b) > eps_linear` 时定义；否则调用该谓词的 match 结果为 `false`。
|
||
|
||
\[
|
||
parallel(a,b):=angleAbs(a,b)\leq\epsilon_{angular}
|
||
\]
|
||
|
||
其中：
|
||
|
||
\[
|
||
angleAbs(a,b)=acos(clamp(|dot(a,b)|,-1,1))
|
||
\]
|
||
|
||
\[
|
||
perpendicular(a,b):=|dot(a,b)|\leq\sin(\epsilon_{angular})
|
||
\]
|
||
|
||
两轴线 `(q1,d1)`、`(q2,d2)` 共轴：
|
||
|
||
```text
|
||
coaxial := parallel(d1,d2)
|
||
and norm((q2-q1) - d1*dot(d1,q2-q1)) <= eps_linear
|
||
```
|
||
|
||
### 4.3 Bbox 相交
|
||
|
||
闭区间 bbox `A`、`B` 相交当且仅当每个轴 `k` 满足：
|
||
|
||
\[
|
||
A_{min,k}\leq B_{max,k}\land B_{min,k}\leq A_{max,k}
|
||
\]
|
||
|
||
`expand(B, e)` 将每个最小坐标减 `e`，每个最大坐标加 `e`。
|
||
|
||
### 4.4 Canonical serialization
|
||
|
||
所有 canonical record 使用 UTF-8 JSON，object key 按 UTF-8 byte order 排序，禁止 NaN 和 Infinity，浮点参数先替换为本文定义的量化整数。
|
||
|
||
```text
|
||
CandidateKey = canonical_json({type, quantized_parameters})
|
||
RawBRepKey = snapshot.sha256
|
||
ProgramKey = canonical_json(program tree with CandidateKey or RawBRepKey leaves)
|
||
```
|
||
|
||
程序树不做交换律重排；`FoldUnion` 的输入排序在第 15 节定义。
|
||
|
||
## 5. 输入分析
|
||
|
||
### 5.1 初始化顺序
|
||
|
||
1. 从导入 shape 计算 bbox；失败返回 `ANALYSIS_FAILED` 和 `RawBRep`。
|
||
2. 计算 `D`；若 `D <= 0` 返回 `INVALID_INPUT`。
|
||
3. 若 bbox 坐标或 `D` 非 finite，返回 `INVALID_INPUT`。
|
||
4. 计算默认配置或读取覆盖配置。
|
||
5. 若 `ConfigValid == false` 返回 `INVALID_CONFIG`。
|
||
6. 创建独立 analysis context，其 deadline 和调用上限来自 `analysis.*`。
|
||
7. 若实体总数超过 `max_analysis_entities`，返回 `ANALYSIS_FAILED`。
|
||
8. 检查 `FiniteBRep`。
|
||
9. 执行本节其余步骤。
|
||
|
||
### 5.2 Solid 有效性
|
||
|
||
```text
|
||
ValidSolid(T) :=
|
||
kernel_is_valid(T) == OK(true)
|
||
and solid_count(T) == 1
|
||
and open_shell_count(T) == 0
|
||
and closed_shell_count(T) >= 1
|
||
and non_manifold_edge_count(T) == 0
|
||
and abs(volume(T)) > eps_volume
|
||
```
|
||
|
||
任一测量调用失败，`ValidSolid` 为 `false`。若为 `false`，返回 `RawBRep(T)` 和 `INVALID_SOLID`。v0.2 不隐式 repair。
|
||
|
||
## 6. 有限证据原子
|
||
|
||
### 6.1 SurfaceAtom
|
||
|
||
对每张 Face 调用固定参数三角化。调用失败时分析失败。对每个面积严格大于 `0` 的三角形 `(a,b,c)` 生成：
|
||
|
||
```text
|
||
SurfaceAtom
|
||
atom_id
|
||
source_face_id
|
||
point = (a+b+c)/3
|
||
oriented_normal
|
||
area = norm(cross(b-a,c-a))/2
|
||
```
|
||
|
||
`oriented_normal` 按 Face orientation 修正。`atom_id` 按 `(source_face_key, Q3(point), Q(area, eps_area), local_triangle_key)` 排序后编号。`local_triangle_key` 是三角形三个量化顶点排序后的 tuple。
|
||
|
||
记集合为 `SA(T)`：
|
||
|
||
\[
|
||
W_S(T)=\sum_{a\in SA(T)}a.area
|
||
\]
|
||
|
||
调用 kernel 计算真实表面积 `A_kernel`。只有满足：
|
||
|
||
\[
|
||
W_S(T)>0
|
||
\]
|
||
|
||
且：
|
||
|
||
\[
|
||
|W_S(T)-A_{kernel}|\leq\max(\epsilon_{area},
|
||
maxMeshAreaRelativeError\cdot A_{kernel})
|
||
\]
|
||
|
||
分析才继续，否则返回 `MESH_COVERAGE_FAILED` 和 `RawBRep`。
|
||
|
||
### 6.2 EdgeAtom
|
||
|
||
跳过 kernel 标记为 degenerated 或 seam 的 Edge。对其余 Edge 计算弧长 `L`。失败时跳过该 Edge 并记录 diagnostic。若 `L <= eps_length`，跳过。
|
||
|
||
\[
|
||
n=\max(1,\lceil L/edgeStep\rceil)
|
||
\]
|
||
|
||
按等弧长区间取中点和单位切向，生成：
|
||
|
||
```text
|
||
EdgeAtom
|
||
atom_id
|
||
source_edge_id
|
||
point
|
||
unit_tangent
|
||
length_weight = L/n
|
||
```
|
||
|
||
任一中点求值失败时跳过整条 Edge。记集合为 `EA(T)`：
|
||
|
||
\[
|
||
W_E(T)=\sum_{e\in EA(T)}e.lengthWeight
|
||
\]
|
||
|
||
### 6.3 AdjacencyAtom
|
||
|
||
对每条非 seam、非 degenerated Edge，取得 incident oriented Face uses。若恰有两个不同 Face，生成：
|
||
|
||
```text
|
||
AdjacencyAtom
|
||
atom_id
|
||
source_edge_id
|
||
face_a_id = min(face keys)
|
||
face_b_id = max(face keys)
|
||
weight = edge_length
|
||
```
|
||
|
||
Edge 长度失败或小于等于 `eps_length` 时不生成。集合记为 `AA(T)`：
|
||
|
||
\[
|
||
W_A(T)=\sum_{r\in AA(T)}r.weight
|
||
\]
|
||
|
||
## 7. 支撑几何 key
|
||
|
||
### 7.1 Plane
|
||
|
||
Plane 用单位法向 `n` 和 `h = dot(n,origin)` 表示。按第 4.1 节规范 `n` 符号；若翻转 `n`，同时翻转 `h`。
|
||
|
||
```text
|
||
PlaneKey = (Q_d(n), Q(h, eps_linear))
|
||
```
|
||
|
||
### 7.2 Axis
|
||
|
||
轴线 `(p,d)` 转换为距原点最近点：
|
||
|
||
\[
|
||
q=p-d\cdot dot(d,p)
|
||
\]
|
||
|
||
规范 `d` 符号后：
|
||
|
||
```text
|
||
AxisKey = (Q_d(d), Q3(q, eps_linear))
|
||
```
|
||
|
||
### 7.3 解析 support
|
||
|
||
```text
|
||
CylinderKey = (AxisKey, Q(radius, eps_radius))
|
||
ConeKey = (AxisKey, Q3(apex, eps_linear), Q(semi_angle, eps_angular))
|
||
SphereKey = (Q3(center, eps_linear), Q(radius, eps_radius))
|
||
TorusKey = (AxisKey, Q(major_radius, eps_radius), Q(minor_radius, eps_radius))
|
||
LineKey = (AxisKey)
|
||
CircleKey = (AxisKey, Q3(center, eps_linear), Q(radius, eps_radius))
|
||
```
|
||
|
||
### 7.4 NURBS exact key
|
||
|
||
v0.2 的 exact key 不试图消除参数反转或重参数化。使用 STEP/kernel 提供的参数化顺序，并将控制点转换到 world coordinates：
|
||
|
||
```text
|
||
NurbsExactKey = SHA256(
|
||
degree_u,
|
||
degree_v,
|
||
periodic_u,
|
||
periodic_v,
|
||
Q(knots_u, 1e-12),
|
||
Q(knots_v, 1e-12),
|
||
multiplicities_u,
|
||
multiplicities_v,
|
||
Q(weights, 1e-12),
|
||
Q3(world_control_points, eps_linear)
|
||
)
|
||
```
|
||
|
||
### 7.5 NURBS 解析约化
|
||
|
||
```text
|
||
RecognizeAnalytic(surface, eps_surface) :=
|
||
OK(CertifiedAnalytic(PlaneParameters, max_error))
|
||
| OK(CertifiedAnalytic(CylinderParameters, max_error))
|
||
| OK(CertifiedAnalytic(ConeParameters, max_error))
|
||
| OK(CertifiedAnalytic(SphereParameters, max_error))
|
||
| OK(CertifiedAnalytic(TorusParameters, max_error))
|
||
| OK(NONE)
|
||
| FAILED
|
||
| TIMEOUT
|
||
| BUDGET_EXHAUSTED
|
||
```
|
||
|
||
只有 backend 能认证整个输入 support surface 在其完整参数域内与返回解析曲面的最大距离不超过 `eps_surface`，并返回 `max_error <= eps_surface` 时才允许 `CertifiedAnalytic`。参数 record 必须包含第 7.1 到 7.3 节 key 所需的全部数值。固定采样只能产生第 12.5 节的近似 evidence，不能把 `NONE` 升级为解析类型。没有认证接口的 backend 必须返回 `OK(NONE)`。
|
||
|
||
## 8. EvidenceGroup 与有限事件
|
||
|
||
### 8.1 Group 代表值
|
||
|
||
每个原始几何 record 为：
|
||
|
||
```text
|
||
EvidenceRecord
|
||
canonical_bucket_key
|
||
exact_parameters
|
||
weight
|
||
source_entity_key
|
||
provenance
|
||
```
|
||
|
||
`provenance` 是有限的 source entity key 集合。按 `canonical_bucket_key` 分组。对同一 source entity 只保留排序键最小的 record；组权重是剩余 record weight 之和；组 provenance 是 record provenance 的并集。代表 record 按以下键取最小：
|
||
|
||
```text
|
||
(-weight, source_entity_key, canonical_json(exact_parameters))
|
||
```
|
||
|
||
候选实际参数只取代表 record 的 `exact_parameters`；bucket 中其他 record 只增加 trigger provenance 和 group weight。
|
||
|
||
Face record 的 `source_entity_key` 和单元素 provenance 为 Face key，weight 为 Face area；Edge 对应 Edge key 和 Edge length；Vertex 对应 Vertex key 和 `eps_area`；bbox corner 对应 `bbox.corner.<0..7>` 和 `0`；world axis 对应 `world.x/y/z` 和 `0`。事件的 `exact_parameters` 包含实际 `value` 或 direction。事件 group 输出显式字段：
|
||
|
||
```text
|
||
EventGroup
|
||
bucket_key
|
||
representative_value_or_direction
|
||
group_weight
|
||
provenance
|
||
```
|
||
|
||
### 8.2 DirectionEvent
|
||
|
||
来源：
|
||
|
||
- Plane Face normal，权重为 Face area。
|
||
- Cylinder/Cone/Torus axis，权重为 Face area。
|
||
- LINE Edge direction，权重为 Edge length。
|
||
- world axes，权重为 `0`，source key 固定为 `world.x/y/z`。
|
||
|
||
按 `Q_d` 分组。若组总正权重 `W > 0`：
|
||
|
||
\[
|
||
d=normalize(\sum_i w_i d_i)
|
||
\]
|
||
|
||
所有 `d_i` 先规范符号。若 `W = 0`，代表方向取 source key 最小 record 的 exact direction。按 `(-group_weight, Q_d(d))` 排序，保留前 `max_direction_clusters` 个。
|
||
|
||
### 8.3 PositionEvent
|
||
|
||
给定单位方向 `d`，产生 record：
|
||
|
||
- 每个 Vertex：`value = dot(d,p)`。
|
||
- 每个 normal 与 `d` 满足 `parallel` 的 Plane：`value = dot(d,origin)`。
|
||
- bbox 八个 corner：`value = dot(d,corner)`。
|
||
|
||
每个来源按第 8.1 节生成完整 EvidenceRecord；`canonical_bucket_key = Q(value,eps_linear)`。按第 8.1 节分组并选择 exact representative value。
|
||
|
||
### 8.4 AxialEvent
|
||
|
||
给定轴 `(q,d)`，产生 record：
|
||
|
||
- 每个 Vertex：`value = dot(d,p-q)`。
|
||
- 每个与该轴满足 `coaxial` 的 CIRCLE Edge：`value = dot(d,center-q)`，weight 为 Edge length。
|
||
- 每个 normal 与 `d` 满足 `parallel` 的 Plane：`value = dot(d,origin-q)`。
|
||
- bbox corner：`value = dot(d,corner-q)`。
|
||
|
||
每个来源按第 8.1 节生成完整 EvidenceRecord；`canonical_bucket_key = Q(value,eps_linear)`。按第 8.1 节分组。
|
||
|
||
DirectionEvent、PositionEvent、AxialEvent 生成 record 时，每增加一个 record 都递增当前 analysis/task 的 `event_record_count`。达到 `max_event_records` 时停止生成更多 record，并返回 `BUDGET_EXHAUSTED`；初始 analysis 因此降级 RawBRep，residual task 因此只允许 RawExpansion。
|
||
|
||
### 8.5 ExtentPair
|
||
|
||
对排序后的不同 event `i < j` 生成：
|
||
|
||
```text
|
||
ExtentPair
|
||
low = min(event_i.value, event_j.value)
|
||
high = max(event_i.value, event_j.value)
|
||
weight = event_i.group_weight + event_j.group_weight
|
||
provenance = union(event_i.provenance, event_j.provenance)
|
||
```
|
||
|
||
只保留 `high-low > eps_linear`。按：
|
||
|
||
```text
|
||
(-weight, -(high-low), Q(low,eps_linear), Q(high,eps_linear))
|
||
```
|
||
|
||
排序，保留前 `max_extent_pairs_per_axis` 个。
|
||
|
||
## 9. 有限候选枚举
|
||
|
||
### 9.0 Primitive 参数 record
|
||
|
||
所有方向均为 world-coordinate unit vector，所有 frame 均为右手正交 frame，所有 extent 满足 `high-low > eps_linear`：
|
||
|
||
```text
|
||
BoxParameters
|
||
frame_origin
|
||
x_axis
|
||
y_axis
|
||
z_axis = cross(x_axis,y_axis)
|
||
x_low, x_high
|
||
y_low, y_high
|
||
z_low, z_high
|
||
|
||
CylinderParameters
|
||
axis_point # 距 world origin 最近点 q
|
||
axis_direction
|
||
radius > eps_radius
|
||
axial_low, axial_high
|
||
|
||
ConeParameters
|
||
axis_point # 距 world origin 最近点 q
|
||
axis_direction
|
||
apex_axial_coordinate
|
||
semi_angle in (eps_angular, pi/2-eps_angular)
|
||
axial_low, axial_high
|
||
|
||
SphereParameters
|
||
center
|
||
radius > eps_radius
|
||
|
||
TorusParameters
|
||
axis_point
|
||
axis_direction
|
||
major_radius
|
||
minor_radius
|
||
```
|
||
|
||
Box 的 world point 为：
|
||
|
||
\[
|
||
frameOrigin+x\cdot xAxis+y\cdot yAxis+z\cdot zAxis
|
||
\]
|
||
|
||
Cylinder/Cone 的 world axial point 为 `axis_point + z*axis_direction`。Cone 在轴坐标 `z` 的半径为：
|
||
|
||
\[
|
||
r(z)=|z-apexAxialCoordinate|\tan(semiAngle)
|
||
\]
|
||
|
||
候选只允许 `r(axial_low)` 或 `r(axial_high)` 至少一个大于 `eps_radius`。这些 record 的字段顺序就是 CandidateKey 的字段顺序。`kernel_construct_primitive` 只接受这些 record。
|
||
|
||
### 9.1 CandidateValid
|
||
|
||
```text
|
||
CandidateValid(H,T) :=
|
||
construction returned OK
|
||
and kernel_is_valid(H) == OK(true)
|
||
and solid_count(H) == 1
|
||
and volume(H) > eps_volume
|
||
and BBox(H) intersects expand(BBox(T), eps_linear)
|
||
and TriggerEntityCount(H) >= min_trigger_entities
|
||
```
|
||
|
||
其中每个 kernel 测量按第 2.3 节执行；任一不是 `OK` 时结果为 `false`。
|
||
|
||
`TriggerEntityCount` 是候选使用的 extent、direction、axis、radius 等 event provenance 中不同 Face/Edge/Vertex key 的数量；`world.*` 和 bbox provenance 不计数。
|
||
|
||
### 9.2 Box
|
||
|
||
1. 从 DirectionEvent 枚举无序三元组，三元组内部按 `Q_d` 排序。
|
||
2. 只保留三对方向均满足 `perpendicular` 的三元组。
|
||
3. 令第一个方向为 `x0`，从第二个方向减去在 `x0` 上的投影后规范化为 `y0`，令 `z0 = normalize(cross(x0,y0))`。
|
||
4. 若 `angleAbs(z0, third_direction) > eps_angular`，丢弃。
|
||
5. frame 固定为右手系 `(x0,y0,z0)`。
|
||
6. frame 按三个 direction group weight 总和降序、frame key 升序排序，只保留前 `max_box_frames` 个。
|
||
7. 对每个 frame axis 生成 PositionEvent 和 ExtentPair。
|
||
8. `frame_origin = (0,0,0)`，三个 extent 均为 world origin 在对应 frame axis 上的投影坐标；枚举三个 ExtentPair 集合的笛卡尔积并构造 oriented Box。
|
||
9. 每个 frame 内按 `(-trigger_weight,-volume,CandidateKey)` 排序，保留前 `max_box_candidates_per_frame` 个。
|
||
|
||
`trigger_weight` 是所有 trigger provenance 对应 record weight 的去重和。
|
||
|
||
### 9.3 Cylinder
|
||
|
||
候选轴和半径来源：
|
||
|
||
- 每个 CylinderKey Face group 的代表参数。
|
||
- 每个 CircleKey group；同一 AxisKey 和 radius bucket 下至少存在两个不同 Circle center axial bucket。
|
||
|
||
对每个 `(axis,radius)` 生成 AxialEvent 和 ExtentPair。Cylinder Face group 只提供 axis/radius，有限 axial extent 一律来自 ExtentPair。每个 pair 构造 `CylinderParameters` 并按 `CandidateValid` 过滤。
|
||
|
||
### 9.4 Cone
|
||
|
||
来源一：每个 ConeKey Face group 的代表参数。
|
||
|
||
来源二：同一 AxisKey 的两个 Circle group `(z1,r1)`、`(z2,r2)`，要求：
|
||
|
||
\[
|
||
|z_1-z_2|>\epsilon_{linear}
|
||
\]
|
||
|
||
且：
|
||
|
||
\[
|
||
|r_1-r_2|>\epsilon_{radius}
|
||
\]
|
||
|
||
计算：
|
||
|
||
\[
|
||
k=(r_2-r_1)/(z_2-z_1)
|
||
\]
|
||
|
||
\[
|
||
z_{apex}=z_1-r_1/k
|
||
\]
|
||
|
||
\[
|
||
semiAngle=atan(|k|)
|
||
\]
|
||
|
||
Cone Face group 只提供 axis/apex/semi-angle，有限 extent 一律来自 AxialEvent 的 ExtentPair。来源二的 `apex_axial_coordinate = z_apex`。截面半径小于 `eps_radius` 时置为 `0`。构造 `ConeParameters` 后按 `CandidateValid` 过滤。
|
||
|
||
### 9.5 Sphere
|
||
|
||
每个 SphereKey Face group 的代表参数生成一个完整 Sphere。v0.2 不从任意圆环拟合 Sphere。
|
||
|
||
### 9.6 Torus
|
||
|
||
每个 TorusKey Face group 的代表参数生成一个完整 Torus，且要求：
|
||
|
||
```text
|
||
major_radius > minor_radius > eps_radius
|
||
```
|
||
|
||
v0.2 不生成 horn torus 或 spindle torus，不从曲率样本拟合 Torus。
|
||
|
||
### 9.7 NURBS 证据记录，不是实体候选
|
||
|
||
NURBS 不进入本节的实体候选列表，不参与 `PrimitiveCost`、signed residual 或 Beam Search。分析阶段只生成：
|
||
|
||
```text
|
||
NurbsEvidenceRecord
|
||
face_ids sharing the same NurbsExactKey
|
||
NurbsCost
|
||
```
|
||
|
||
v0.2 只按 `NurbsExactKey` 分组，不计算一般 NURBS 的 pairwise 等价关系。
|
||
|
||
### 9.8 去重和预算
|
||
|
||
候选只按 `CandidateKey` 去重。相同 key 合并 trigger provenance。v0.2 不调用 Boolean 做候选几何去重。
|
||
|
||
每种类型按第 13.3 节排序后保留前 `max_candidates_per_type` 个。
|
||
|
||
每个 task 在尝试构造候选前递增 `candidate_attempt_count`；在候选专属 kernel 调用前递增 `candidate_kernel_call_count`。达到 `max_candidate_attempts_per_task` 或 `max_candidate_kernel_calls_per_task` 后，停止该 task 的候选枚举，并继续保留其无条件 RawExpansion。该规则同时限制 Circle pair、Cone pair 和 Box extent 笛卡尔积的实际尝试数。
|
||
|
||
## 10. 先验与描述代价
|
||
|
||
### 10.1 PrimitiveCost
|
||
|
||
```text
|
||
ParameterCodeUnits(Box) = 9
|
||
ParameterCodeUnits(Cylinder) = 8
|
||
ParameterCodeUnits(Cone) = 9
|
||
ParameterCodeUnits(Sphere) = 4
|
||
ParameterCodeUnits(Torus) = 9
|
||
```
|
||
|
||
```text
|
||
PrimitiveCost(H) =
|
||
configured_type_cost(H.type)
|
||
+ scalar_parameter_cost * ParameterCodeUnits(H.type)
|
||
```
|
||
|
||
`ParameterCodeUnits` 是 v0.2 先验表中的版本化整数，不声称等于参数 record 字段数或最小几何自由度。
|
||
|
||
### 10.2 NurbsCost
|
||
|
||
```text
|
||
NurbsCost(face) =
|
||
type_cost_nurbs_face
|
||
+ 0.02 * control_point_count
|
||
+ 0.01 * (knot_u_count + knot_v_count)
|
||
+ 0.01 * non_unit_weight_count
|
||
+ 0.02 * degree_u * degree_v
|
||
+ 0.05 * trim_edge_count
|
||
```
|
||
|
||
同一 `NurbsExactKey` group 的代价为一张 support 的 `NurbsCost` 加 `0.1 * (face_count-1)`。
|
||
|
||
### 10.3 RawBRepCost
|
||
|
||
```text
|
||
RawBRepCost(analysis_or_raw_stats) =
|
||
type_cost_raw_brep
|
||
+ sum(NurbsCost(record) for nurbs_face_records)
|
||
+ 0.20 * analytic_face_count
|
||
+ 0.05 * edge_count
|
||
+ 0.01 * vertex_count
|
||
```
|
||
|
||
### 10.4 LeafCost
|
||
|
||
```text
|
||
LeafCost(primitive) = PrimitiveCost(primitive)
|
||
LeafCost(RawBRep(...,raw_stats)) = RawBRepCost(raw_stats)
|
||
```
|
||
|
||
这些代价是“常见性”的唯一规范表示。数值越低，先验偏好越高。
|
||
|
||
## 11. 点、法向和 Edge 投影谓词
|
||
|
||
### 11.1 ProjectFace
|
||
|
||
```text
|
||
ProjectFace(point, face) := kernel_nearest_point_on_trimmed_face(point, face)
|
||
```
|
||
|
||
成功值包含：
|
||
|
||
```text
|
||
distance
|
||
projected_point
|
||
all_outward_normals_at_projection
|
||
```
|
||
|
||
投影位于 smooth interior 时 normal 集合大小为 `1`；位于 Edge/Vertex 时包含所有 incident Face outward normals；无法取得 normal 时调用失败。
|
||
|
||
### 11.2 BoundaryExplainsOnFace
|
||
|
||
```text
|
||
BoundaryExplainsOnFace(atom, face) :=
|
||
ProjectFace(atom.point, face) == OK(p)
|
||
and p.distance <= eps_surface
|
||
and exists n in p.all_outward_normals_at_projection:
|
||
angle(atom.oriented_normal, n) <= eps_normal
|
||
```
|
||
|
||
### 11.3 ProjectEdge
|
||
|
||
```text
|
||
EdgeExplainsOnEdge(atom, edge) :=
|
||
kernel_nearest_point_on_edge(atom.point, edge) == OK(p)
|
||
and p.distance <= eps_surface
|
||
and angleAbs(atom.unit_tangent, p.unit_tangent) <= eps_normal
|
||
```
|
||
|
||
## 12. 支撑面匹配
|
||
|
||
### 12.1 无向 support 匹配
|
||
|
||
`SupportExplains` 故意忽略材料方向，因为同一个 Cylinder support 可以是凸台外壁，也可以在 `Subtract` 后成为孔壁。方向只在候选实际边界和最终 leaf ownership 中检查。
|
||
|
||
Plane：
|
||
|
||
\[
|
||
|dot(n,a.point)-h|\leq\epsilon_{surface}
|
||
\]
|
||
|
||
且 `angleAbs(n,a.oriented_normal) <= eps_normal`。
|
||
|
||
Cylinder：令：
|
||
|
||
\[
|
||
v=a.point-q-d\cdot dot(d,a.point-q)
|
||
\]
|
||
|
||
要求：
|
||
|
||
\[
|
||
|\|v\|-r|\leq\epsilon_{surface}
|
||
\]
|
||
|
||
且 `norm(v) > eps_linear`，并满足 `angleAbs(v/norm(v),a.oriented_normal) <= eps_normal`。
|
||
|
||
Cone、Sphere、Torus：调用无限支撑面的 kernel projection，要求 distance 不超过 `eps_surface`，且 projected normal 与 atom normal 的 `angleAbs` 不超过 `eps_normal`。
|
||
|
||
```text
|
||
SupportExplains(H,a) :=
|
||
exists support s of primitive H: support_match(s,a)
|
||
```
|
||
|
||
### 12.2 实际边界匹配
|
||
|
||
```text
|
||
BoundaryExplains(H,a) :=
|
||
exists boundary Face f of H: BoundaryExplainsOnFace(a,f)
|
||
```
|
||
|
||
### 12.3 Edge 匹配
|
||
|
||
`NaturalEdges(H)` 是 primitive 构造结果中排除 seam 和 degenerated Edge 后的有限 Edge 集合。
|
||
|
||
```text
|
||
EdgeExplains(H,e) :=
|
||
exists g in NaturalEdges(H): EdgeExplainsOnEdge(e,g)
|
||
```
|
||
|
||
### 12.4 FaceMap
|
||
|
||
对目标 Face `f` 和候选边界 Face `b`：
|
||
|
||
\[
|
||
M(f,b)=\sum_{a\in SA(T),a.sourceFace=f}
|
||
a.area\cdot I[BoundaryExplainsOnFace(a,b)]
|
||
\]
|
||
|
||
`FaceMap(f,H)` 取 `M(f,b)` 最大的候选 Face；最大值小于 `eps_area` 时为 `NONE`。同分时按：
|
||
|
||
```text
|
||
BoundaryFaceKey = (support_key,
|
||
Q3(face_centroid, eps_linear),
|
||
Q(face_area, eps_area),
|
||
construction_local_face_id)
|
||
```
|
||
|
||
取 key 最小者。`construction_local_face_id` 由 primitive builder 按固定面角色分配，不使用 kernel 枚举序号。
|
||
|
||
## 13. 候选解释与局部分数
|
||
|
||
### 13.1 Bitset
|
||
|
||
```text
|
||
CandidateExplanation
|
||
support_surface_atom_bits[a] = SupportExplains(H,a)
|
||
boundary_surface_atom_bits[a] = BoundaryExplains(H,a)
|
||
edge_atom_bits[e] = EdgeExplains(H,e)
|
||
adjacency_atom_bits[r] = AdjacencyExplains(H,r)
|
||
```
|
||
|
||
`AdjacencyExplains(H,r)` 当且仅当：
|
||
|
||
- `FaceMap(r.face_a,H)` 和 `FaceMap(r.face_b,H)` 均不是 `NONE`。
|
||
- 两个映射结果不同。
|
||
- 两个候选 Face 在候选 B-Rep 中共享至少一条非 degenerated Edge。
|
||
|
||
### 13.2 覆盖率
|
||
|
||
\[
|
||
C_S=\frac{\sum_a a.area\cdot I[supportBits[a]]}{W_S(T)}
|
||
\]
|
||
|
||
\[
|
||
C_B=\frac{\sum_a a.area\cdot I[boundaryBits[a]]}{W_S(T)}
|
||
\]
|
||
|
||
若 `W_E(T)>0`：
|
||
|
||
\[
|
||
C_E=\frac{\sum_e e.lengthWeight\cdot I[edgeBits[e]]}{W_E(T)}
|
||
\]
|
||
|
||
否则 `C_E=0` 且局部分数中的 Edge reward 置 `0`。
|
||
|
||
若 `W_A(T)>0`：
|
||
|
||
\[
|
||
C_A=\frac{\sum_r r.weight\cdot I[adjacencyBits[r]]}{W_A(T)}
|
||
\]
|
||
|
||
否则 `C_A=0` 且局部分数中的 adjacency reward 置 `0`。
|
||
|
||
### 13.3 LocalScore
|
||
|
||
\[
|
||
LocalScore(H,T)=
|
||
rewardSupport\cdot C_S+
|
||
rewardBoundary\cdot C_B+
|
||
rewardEdge'\cdot C_E+
|
||
rewardAdjacency'\cdot C_A-
|
||
penaltyLeafCost\cdot PrimitiveCost(H)
|
||
\]
|
||
|
||
候选只在 `C_S >= min_support_coverage` 时保留。排序键：
|
||
|
||
```text
|
||
(-LocalScore, -C_S, -C_B, PrimitiveCost, CandidateKey)
|
||
```
|
||
|
||
每种类型保留前 `max_candidates_per_type` 个，合并后保留前 `boolean_prefilter_top_m` 个。
|
||
|
||
## 14. Signed residual
|
||
|
||
对当前任务 solid `S` 和候选 `H`，连续执行两个 kernel Boolean：
|
||
|
||
```text
|
||
RplusResult: BooleanShape = regularized_cut(S,H)
|
||
RminusResult: BooleanShape = regularized_cut(H,S)
|
||
```
|
||
|
||
调用前必须为两个 Boolean 分别成功 reserve budget。任一结果失败时淘汰候选。
|
||
|
||
对 `EMPTY` 使用空 component list；对 `NONEMPTY(shape)` 调用 `components(shape)`。调用失败时淘汰候选。每个非空 component 必须满足 `ValidSolid`。体积小于等于 `eps_volume` 的 component 不进入列表，删除体积累加为 `discardedVolume`。若：
|
||
|
||
\[
|
||
discardedVolume>\epsilon_{volume}
|
||
\]
|
||
|
||
则淘汰候选。
|
||
|
||
剩余 component 分别记为：
|
||
|
||
```text
|
||
P = sorted components of Rplus
|
||
M = sorted components of Rminus
|
||
```
|
||
|
||
每个剩余 component 立即执行第 15.1 节 `AnalyzeResidual`。任一分析失败时淘汰候选。排序键为 analysis 中的 `snapshot.sha256`。
|
||
|
||
## 15. 程序模板状态转移
|
||
|
||
### 15.1 ResidualAnalysis
|
||
|
||
```text
|
||
ResidualAnalysis
|
||
shape # 只在当前进程计算期间使用
|
||
snapshot: BRepSnapshot # 可序列化、可重放
|
||
surface_atoms
|
||
edge_atoms
|
||
adjacency_atoms
|
||
support_groups
|
||
direction_events
|
||
face_count
|
||
edge_count
|
||
vertex_count
|
||
analytic_face_count
|
||
nurbs_face_count
|
||
raw_stats
|
||
volume
|
||
surface_area
|
||
```
|
||
|
||
```text
|
||
AnalyzeResidual(S,config,context) :=
|
||
ValidSolid(S)
|
||
+ SnapshotOf(S)
|
||
+ 第 6 至 8 节全部分析
|
||
```
|
||
|
||
结果是 `KernelResult[ResidualAnalysis]`。所有测量只在这里执行并缓存；候选排序、cost、proxy、task 选择和 StateKey 不允许再次隐式调用 kernel。初始 target 也产生相同结构的 `ResidualAnalysis`。
|
||
|
||
### 15.2 FoldUnion
|
||
|
||
统一排序函数：
|
||
|
||
```text
|
||
UnionOrderKey(primitive leaf) = (0, CandidateKey)
|
||
UnionOrderKey(RawBRep leaf) = (1, RawBRepKey)
|
||
UnionOrderKey(Slot) = (2, slot_id)
|
||
UnionOrderKey(composite Program) = (3, ProgramKey)
|
||
```
|
||
|
||
输入按 `UnionOrderKey` 排序。
|
||
|
||
```text
|
||
FoldUnion([]) = EMPTY
|
||
FoldUnion([x]) = x
|
||
FoldUnion([x1,...,xn]) = Union(...Union(Union(x1,x2),x3)...,xn)
|
||
```
|
||
|
||
`EMPTY` 只用于构造规则，不是 `Program` 节点。
|
||
|
||
### 15.3 CandidateExpansion
|
||
|
||
设 `P` 有 `p` 个 components，`M` 有 `m` 个 components。为每个 component 创建唯一 Slot，ID 为：
|
||
|
||
```text
|
||
SHA256(parent_slot_id, sign, component_analysis.snapshot.sha256,
|
||
same_fingerprint_ordinal)
|
||
```
|
||
|
||
其中 `sign` 只用于 ID，取 `PLUS` 或 `MINUS`；ordinal 是排序后同 fingerprint 的从零计数。
|
||
|
||
```text
|
||
base = FoldUnion([H] + plus_slots)
|
||
replacement = base if m == 0
|
||
replacement = Subtract(base,
|
||
FoldUnion(minus_slots)) if m > 0
|
||
```
|
||
|
||
将当前 `Slot` 替换为 `replacement`。每个新 Slot 对应：
|
||
|
||
```text
|
||
ResidualTask
|
||
slot_id
|
||
analysis: ResidualAnalysis
|
||
depth = parent.depth + 1
|
||
```
|
||
|
||
若新 task 数使状态的 `pending_task_count > max_pending_tasks_per_state`，丢弃该 CandidateExpansion，只保留父 task 的 RawExpansion。
|
||
|
||
新插入 Boolean 节点数：
|
||
|
||
```text
|
||
union_count = p + max(m-1, 0)
|
||
subtract_count = 1 if m > 0 else 0
|
||
```
|
||
|
||
立即增加的 committed cost：
|
||
|
||
```text
|
||
PrimitiveCost(H)
|
||
+ union_count * operation_cost_union
|
||
+ subtract_count * operation_cost_subtract
|
||
```
|
||
|
||
### 15.4 RawExpansion
|
||
|
||
`task.analysis` 已含 `SnapshotOf(task.analysis.shape)` 的结果。将当前 `Slot` 替换为 `RawBRep(task.analysis.snapshot, len(snapshot.bytes), task.analysis.raw_stats)`，删除该 task，立即增加：
|
||
|
||
```text
|
||
RawBRepCost(task.analysis)
|
||
```
|
||
|
||
### 15.5 成本不变量
|
||
|
||
对任一搜索状态：
|
||
|
||
```text
|
||
committed_cost =
|
||
sum(cost of every committed leaf)
|
||
+ sum(cost of every committed Boolean node)
|
||
```
|
||
|
||
当没有 Slot 时：
|
||
|
||
```text
|
||
committed_cost == ProgramCost(completed_program)
|
||
```
|
||
|
||
## 16. Residual 代理代价和展开门槛
|
||
|
||
### 16.1 ResidualProxyCost
|
||
|
||
```text
|
||
ResidualProxyCost(analysis) =
|
||
1.00 * solid_count
|
||
+ 0.20 * analytic_face_count
|
||
+ 0.50 * nurbs_face_count
|
||
+ 0.02 * edge_count
|
||
+ 0.01 * vertex_count
|
||
```
|
||
|
||
component list 的 proxy 是每个 component proxy 之和。
|
||
|
||
### 16.2 ExpansionEstimate
|
||
|
||
\[
|
||
ExpansionEstimate=
|
||
PrimitiveCost(H)+
|
||
unionCount\cdot operationCostUnion+
|
||
subtractCount\cdot operationCostSubtract+
|
||
Proxy(P)+Proxy(M)+
|
||
unmatchedSupportPenalty\cdot(1-C_S)+
|
||
unmatchedBoundaryPenalty\cdot(1-C_B)+
|
||
unmatchedEdgePenalty'\cdot(1-C_E)
|
||
\]
|
||
|
||
若 `W_E=0`，最后一项为 `0`。
|
||
|
||
只有满足：
|
||
|
||
\[
|
||
ExpansionEstimate\leq RawBRepCost(currentTask.analysis)+expansionMargin
|
||
\]
|
||
|
||
的候选才执行第 15.3 节状态转移。
|
||
|
||
## 17. 有界 Beam Search
|
||
|
||
### 17.1 SearchState
|
||
|
||
```text
|
||
SearchState
|
||
template
|
||
tasks_by_slot_id
|
||
committed_cost
|
||
estimated_remaining_cost
|
||
state_key
|
||
```
|
||
|
||
```text
|
||
estimated_remaining_cost =
|
||
sum(MinLeafCost for each pending task)
|
||
```
|
||
|
||
```text
|
||
MinLeafCost = min(
|
||
type_cost_box + 9*scalar_parameter_cost,
|
||
type_cost_cylinder + 8*scalar_parameter_cost,
|
||
type_cost_cone + 9*scalar_parameter_cost,
|
||
type_cost_sphere + 4*scalar_parameter_cost,
|
||
type_cost_torus + 9*scalar_parameter_cost,
|
||
type_cost_raw_brep
|
||
)
|
||
```
|
||
|
||
该值只用于排序；不声称是包含 Boolean 操作的严格数学下界。
|
||
|
||
### 17.2 StateKey
|
||
|
||
```text
|
||
state_key = SHA256(
|
||
canonical serialization of template,
|
||
sorted tuples(slot_id, task.depth, task.analysis.snapshot.sha256)
|
||
)
|
||
```
|
||
|
||
同一 `state_key` 只保留 `committed_cost` 最小者；同分保留 template serialization 字典序最小者。
|
||
|
||
### 17.3 任务选择
|
||
|
||
从 pending task 中按以下键取最小：
|
||
|
||
```text
|
||
(-RawBRepCost(task.analysis),
|
||
-task.analysis.volume,
|
||
task.analysis.snapshot.sha256,
|
||
slot_id)
|
||
```
|
||
|
||
### 17.4 单状态展开
|
||
|
||
```text
|
||
if task.depth >= max_task_depth:
|
||
children = [RawExpansion(state, task)]
|
||
else:
|
||
children = every accepted CandidateExpansion
|
||
plus one unconditional RawExpansion
|
||
```
|
||
|
||
展开一个状态前检查 `expanded_states + 1 <= max_expanded_states`。每个 kernel 调用由 `KernelContext.try_reserve` 单独检查，因此 Boolean 和总调用硬上限不会超出。
|
||
|
||
### 17.5 Frontier
|
||
|
||
算法每次从 frontier 取排序键最小的一个状态展开，再将 children 放回 frontier。排序键：
|
||
|
||
```text
|
||
(
|
||
committed_cost + estimated_remaining_cost,
|
||
sum(RawBRepCost(task.analysis) for pending tasks),
|
||
pending_task_count,
|
||
state_key
|
||
)
|
||
```
|
||
|
||
插入 children、去重、排序后只保留前 `beam_width` 个状态。
|
||
|
||
### 17.6 搜索终止
|
||
|
||
搜索上下文保存唯一 `termination_reason`：
|
||
|
||
```text
|
||
FRONTIER_EMPTY
|
||
STATE_LIMIT
|
||
BOOLEAN_LIMIT
|
||
KERNEL_CALL_LIMIT
|
||
SEARCH_TIMEOUT
|
||
ENOUGH_COMPLETED_PROGRAMS
|
||
```
|
||
|
||
循环开始及每次 kernel reserve 前更新该值。达到任何预算后不再生成候选。若一个状态已从 frontier 弹出但尚未完成展开，将该未修改状态加入 `fallbackStates`；已经完整生成的 children 保留在 frontier。把 `frontier union fallbackStates` 中每个状态的全部 pending Slot 按 slot ID 升序执行 RawExpansion，得到完整程序。若 frontier 正常变空且 termination reason 尚未设置，则设置为 `FRONTIER_EMPTY`。
|
||
|
||
完成程序按 `(ProgramCost,ProgramKey)` 去重，只保留前 `max_completed_programs_to_validate` 个。
|
||
|
||
### 17.7 显式调用上界
|
||
|
||
若实际展开状态数为 `S <= max_expanded_states`，每状态经过预筛选的候选数为 `P <= boolean_prefilter_top_m`，signed residual 最多调用：
|
||
|
||
\[
|
||
2SP
|
||
\]
|
||
|
||
次 Boolean。实际数量同时受 `max_search_boolean_calls` 限制。候选构造、投影和测量计入 `max_search_total_kernel_calls`。最终程序重放和验证使用独立 validation context，不消费搜索预算。
|
||
|
||
## 18. 完整程序代价
|
||
|
||
```text
|
||
ProgramCost(primitive) = PrimitiveCost(primitive)
|
||
ProgramCost(RawBRep(...,raw_stats)) = RawBRepCost(raw_stats)
|
||
ProgramCost(Union(A,B)) = ProgramCost(A)+ProgramCost(B)+operation_cost_union
|
||
ProgramCost(Subtract(A,B)) = ProgramCost(A)+ProgramCost(B)+operation_cost_subtract
|
||
```
|
||
|
||
## 19. 完整程序验证
|
||
|
||
### 19.1 重放
|
||
|
||
整个 validation 阶段创建一个共享 `validationContext`；所有完成程序和最终 RawBRep fallback 共用它的 deadline 和调用计数。依次执行按 `(ProgramCost,ProgramKey)` 排序的程序；context 到期或预算耗尽后不再验证后续程序。
|
||
|
||
对一个程序只执行一次 `Render(P)` 并保存 `ReplayResult = R`。失败时：
|
||
|
||
```text
|
||
ValidProgram(P,T) = false
|
||
```
|
||
|
||
### 19.2 Symmetric difference
|
||
|
||
成功重放结果为 `R`：
|
||
|
||
```text
|
||
D1: BooleanShape = regularized_cut(T,R)
|
||
D2: BooleanShape = regularized_cut(R,T)
|
||
symdiff_volume = volume(D1)+volume(D2) # volume(EMPTY)=0
|
||
```
|
||
|
||
任一调用失败则验证失败。
|
||
|
||
```text
|
||
VolumeEquivalent := symdiff_volume <= eps_volume
|
||
```
|
||
|
||
### 19.3 双向边界距离和法向
|
||
|
||
用第 6.1 节相同配置生成 `SA(R)`，并对 mesh area 执行相同覆盖检查。对 `SA(T)` 中每个 atom 投影到 `boundary(R)`，对 `SA(R)` 中每个 atom 投影到 `boundary(T)`。
|
||
|
||
每次 projection 必须成功。距离集合 `Dists` 和最小有向法向误差集合 `Angles`：
|
||
|
||
```text
|
||
distance = nearest boundary distance
|
||
angle = min(angle(atom.oriented_normal,n)
|
||
for n in all outward normals at projection)
|
||
```
|
||
|
||
两个 atom 集合都非空，因此：
|
||
|
||
\[
|
||
maxBoundaryDistance=\max(Dists)
|
||
\]
|
||
|
||
\[
|
||
rmsBoundaryDistance=\sqrt{
|
||
\frac{\sum_i area_i\cdot distance_i^2}{\sum_i area_i}}
|
||
\]
|
||
|
||
\[
|
||
maxNormalError=\max(Angles)
|
||
\]
|
||
|
||
```text
|
||
BoundaryEquivalent := maxBoundaryDistance <= eps_surface
|
||
NormalEquivalent := maxNormalError <= eps_normal
|
||
```
|
||
|
||
`rmsBoundaryDistance` 只作为输出指标，不参与 v0.2 acceptance。
|
||
|
||
### 19.4 可计算 topology signature
|
||
|
||
v0.2 不用原始 `V-E+F` 计算 Euler characteristic。定义：
|
||
|
||
```text
|
||
TopologySignature(S) = (
|
||
solid_count(S),
|
||
closed_shell_count(S),
|
||
open_shell_count(S),
|
||
non_manifold_edge_count(S)
|
||
)
|
||
```
|
||
|
||
任一计数调用失败则验证失败。
|
||
|
||
```text
|
||
TopologySignatureMatches := TopologySignature(T) == TopologySignature(R)
|
||
```
|
||
|
||
### 19.5 ValidProgram
|
||
|
||
```text
|
||
ValidProgram(P,T) :=
|
||
ReplayResult R exists
|
||
and kernel_is_valid(R) == OK(true)
|
||
and VolumeEquivalent
|
||
and BoundaryEquivalent
|
||
and NormalEquivalent
|
||
and TopologySignatureMatches
|
||
```
|
||
|
||
`ValidProgram` 是 acceptance profile 名称，含义仅为本节 finite tests 在给定配置下通过，不表示符号等价或完整 Hausdorff/topology 证明。
|
||
|
||
## 20. SurfaceAtom 归属与有效解释
|
||
|
||
### 20.1 Leaf polarity
|
||
|
||
从程序根向叶递归：
|
||
|
||
```text
|
||
polarity(root) = +1
|
||
polarity(Union.left/right) = polarity(parent)
|
||
polarity(Subtract.left) = polarity(parent)
|
||
polarity(Subtract.right) = -polarity(parent)
|
||
```
|
||
|
||
### 20.2 LeafSupportEvidence
|
||
|
||
对 primitive 或 RawBRep 叶节点 `L`，将其支撑面投影法向乘 `polarity(L)`：
|
||
|
||
```text
|
||
LeafSupportEvidence(L,a) :=
|
||
exists support face f of L:
|
||
projection of a.point to support(f) succeeds
|
||
and distance <= eps_surface
|
||
and exists normal n at projection:
|
||
angle(a.oriented_normal, polarity(L)*n) <= eps_normal
|
||
```
|
||
|
||
支撑面使用未裁剪 support，因此 Boolean 改变 trim 后仍可产生解释证据。这个 predicate 不声称该叶节点是原始历史来源，也不证明该 support 在 Boolean 中对最终边界有唯一贡献。
|
||
|
||
### 20.3 唯一 owner
|
||
|
||
对每个目标 SurfaceAtom 枚举有限叶节点集合。满足 `LeafSupportEvidence` 的叶节点按：
|
||
|
||
```text
|
||
(
|
||
0 if primitive else 1,
|
||
LeafCost,
|
||
-leaf_depth,
|
||
leaf_program_key
|
||
)
|
||
```
|
||
|
||
取最小者。输出字段名为 `support_evidence_owner`；没有匹配者时为 `NONE`。
|
||
|
||
### 20.4 ValidExplanation
|
||
|
||
```text
|
||
ValidExplanation(P,T) :=
|
||
ValidProgram(P,T)
|
||
and every a in SA(T) has support_evidence_owner != NONE
|
||
```
|
||
|
||
本文中的“100% 解释”严格指：第 6.1 节有限 SurfaceAtom 集合全部有 support evidence，并且第 19 节 acceptance profile 通过；不表示连续曲面上的数学全称命题。第 6.1 节同时限制离散 surface area 与 kernel surface area 的差值。
|
||
|
||
## 21. Edge 和 adjacency 节点归属
|
||
|
||
Edge 和 adjacency 可能由 Boolean 生成，因此不强制归属到叶节点。
|
||
|
||
### 21.1 节点重放缓存
|
||
|
||
完整程序验证时缓存每个语法树节点的 `Render(node)`。节点深度从根为 `0` 向下递增。
|
||
|
||
### 21.2 EdgeOwner
|
||
|
||
```text
|
||
NodeExplainsEdge(node,e) :=
|
||
exists non-seam, non-degenerated Edge g in Render(node):
|
||
EdgeExplainsOnEdge(e,g)
|
||
```
|
||
|
||
候选 node 按 `(-node_depth,node_program_key)` 取最小。最终 root 若仍不能解释，则 owner 为 `UNATTRIBUTED`。
|
||
|
||
### 21.3 AdjacencyOwner
|
||
|
||
对每个 node 的 rendered shape，用第 12.4 节方式把目标两个 Face 映射到 node result Face：
|
||
|
||
```text
|
||
NodeExplainsAdjacency(node,r) :=
|
||
both FaceMap values exist and differ
|
||
and the mapped result Faces share a non-degenerated Edge
|
||
```
|
||
|
||
按 `(-node_depth,node_program_key)` 选择 owner。失败时为 `UNATTRIBUTED`。
|
||
|
||
Edge 或 adjacency 的 `UNATTRIBUTED` 数量进入输出，但 v0.2 不把它们加入 `ValidExplanation`；几何正确性由第 19 节约束。
|
||
|
||
## 22. 最终选择
|
||
|
||
先对最多 `max_completed_programs_to_validate` 个完成程序执行第 19、20 节。令：
|
||
|
||
```text
|
||
VP = finite set of programs with ValidExplanation == true
|
||
```
|
||
|
||
若 `VP` 非空，排序键为：
|
||
|
||
```text
|
||
(
|
||
ProgramCost,
|
||
RawBRep_leaf_count,
|
||
total_NURBS_face_count_inside_RawBRep,
|
||
Boolean_node_count,
|
||
ProgramKey
|
||
)
|
||
```
|
||
|
||
返回最小者，status 为 `VALID_EXPLANATION`。
|
||
|
||
若 `VP` 为空，验证 `RawBRep(T)`。若其 `ValidExplanation` 为 true，返回它，status 为 `RAW_BREP_ONLY`；否则返回 `FINAL_VALIDATION_FAILED`。
|
||
|
||
## 23. 主算法伪代码
|
||
|
||
```python
|
||
def reverse_step(target, overrides=None):
|
||
bbox = kernel_bbox(target)
|
||
if not bbox.ok:
|
||
return snapshot_or_failure(target, "ANALYSIS_FAILED")
|
||
if not bbox.finite or bbox.diagonal <= 0:
|
||
return snapshot_or_failure(target, "INVALID_INPUT")
|
||
|
||
config = resolve_config(target, bbox, overrides)
|
||
if not config_valid(config):
|
||
return failure("INVALID_CONFIG")
|
||
|
||
analysis_ctx = KernelContext.for_analysis(config)
|
||
analysis = analyze_residual(target, config, analysis_ctx)
|
||
if not analysis.ok:
|
||
return snapshot_or_failure(target, analysis.status)
|
||
|
||
search_ctx = KernelContext.for_search(config)
|
||
initial_slot = Slot(id=sha256("root"))
|
||
initial_task = ResidualTask(
|
||
slot_id=initial_slot.id,
|
||
analysis=analysis.value,
|
||
depth=0,
|
||
)
|
||
frontier = [SearchState(
|
||
template=initial_slot,
|
||
tasks={initial_slot.id: initial_task},
|
||
committed_cost=0,
|
||
)]
|
||
completed = []
|
||
fallback_states = []
|
||
expanded_states = 0
|
||
|
||
while frontier and not search_ctx.stopped:
|
||
state = pop_min(frontier, key=frontier_sort_key)
|
||
|
||
if not state.tasks:
|
||
completed.append(state.template)
|
||
if len(completed) >= config.search.max_completed_programs_to_validate:
|
||
search_ctx.stop("ENOUGH_COMPLETED_PROGRAMS")
|
||
continue
|
||
|
||
if expanded_states >= config.search.max_expanded_states:
|
||
search_ctx.stop("STATE_LIMIT")
|
||
fallback_states.append(state)
|
||
break
|
||
|
||
task = select_task(state.tasks)
|
||
expanded_states += 1
|
||
children = []
|
||
|
||
if task.depth < config.search.max_task_depth:
|
||
candidates = enumerate_candidates(task.analysis, config, search_ctx)
|
||
explanations = compute_explanations(candidates, task.analysis, config, search_ctx)
|
||
ranked = rank_and_limit(explanations, config)
|
||
|
||
for candidate, explanation in ranked:
|
||
residuals = signed_residuals(task.analysis, candidate, config, search_ctx)
|
||
if not residuals.ok:
|
||
if search_ctx.stopped:
|
||
break
|
||
continue
|
||
if expansion_estimate(candidate, explanation, residuals, config) \
|
||
> raw_brep_cost(task.analysis, config) + config.score.expansion_margin:
|
||
continue
|
||
children.append(candidate_expansion(
|
||
state, task, candidate, residuals, config
|
||
))
|
||
|
||
if search_ctx.stopped:
|
||
fallback_states.append(state)
|
||
break
|
||
|
||
children.append(raw_expansion(state, task, config))
|
||
frontier = deduplicate(frontier + children)
|
||
frontier.sort(key=frontier_sort_key)
|
||
frontier = frontier[:config.search.beam_width]
|
||
|
||
if not search_ctx.termination_reason:
|
||
search_ctx.stop("FRONTIER_EMPTY")
|
||
|
||
completed.extend(materialize_all_slots_as_raw(
|
||
deduplicate(frontier + fallback_states), config
|
||
))
|
||
completed = deduplicate_and_sort_programs(completed, config)
|
||
completed = completed[:config.search.max_completed_programs_to_validate]
|
||
|
||
valid = []
|
||
validation_ctx = KernelContext.for_validation(config)
|
||
for program in completed:
|
||
if validation_ctx.stopped:
|
||
break
|
||
metrics = validate_program_and_assign_atoms(
|
||
program, target, analysis, config, validation_ctx
|
||
)
|
||
if metrics.valid_explanation:
|
||
valid.append((final_program_sort_key(program, metrics), program, metrics))
|
||
|
||
if valid:
|
||
valid.sort(key=lambda x: x[0])
|
||
return result(valid[0], search_ctx.termination_reason)
|
||
|
||
return validate_and_return_raw_brep(
|
||
target, analysis, config, validation_ctx
|
||
)
|
||
```
|
||
|
||
`snapshot_or_failure` 创建一个独立、只允许一次 `SnapshotOf` 的 emergency context；成功时返回 `RawBRep`，失败时 `program = null`。这条 emergency 调用及其 deadline 单独写入结果，不能复用已经耗尽的阶段 context。
|
||
|
||
## 24. 状态与诊断枚举
|
||
|
||
```text
|
||
INVALID_CONFIG
|
||
INVALID_INPUT
|
||
ANALYSIS_FAILED
|
||
INVALID_SOLID
|
||
MESH_COVERAGE_FAILED
|
||
CANDIDATE_CONSTRUCTION_FAILED
|
||
BOOLEAN_FAILED
|
||
BOOLEAN_TIMEOUT
|
||
NUMERICALLY_UNSTABLE
|
||
STATE_LIMIT
|
||
BOOLEAN_LIMIT
|
||
KERNEL_CALL_LIMIT
|
||
SEARCH_TIMEOUT
|
||
FRONTIER_EMPTY
|
||
ENOUGH_COMPLETED_PROGRAMS
|
||
RAW_BREP_ONLY
|
||
FINAL_VALIDATION_FAILED
|
||
VALID_EXPLANATION
|
||
```
|
||
|
||
自由文本 diagnostic 不参与控制流。
|
||
|
||
## 25. 输出结构
|
||
|
||
```text
|
||
ExplanationResult
|
||
status
|
||
search_termination_reason
|
||
input_fingerprint
|
||
config
|
||
program
|
||
program_key
|
||
program_cost
|
||
candidate_records
|
||
surface_atom_owners
|
||
edge_atom_owners
|
||
adjacency_atom_owners
|
||
validation_metrics
|
||
kernel_call_counts
|
||
diagnostics
|
||
```
|
||
|
||
`validation_metrics` 至少包含：
|
||
|
||
```text
|
||
symdiff_volume
|
||
max_boundary_distance
|
||
rms_boundary_distance
|
||
max_normal_error
|
||
topology_signature_input
|
||
topology_signature_result
|
||
surface_atom_count
|
||
owned_surface_atom_count
|
||
unattributed_edge_atom_count
|
||
unattributed_adjacency_atom_count
|
||
valid_program
|
||
valid_explanation
|
||
```
|
||
|
||
## 26. MVP 模块
|
||
|
||
实现模块和唯一输入输出如下：
|
||
|
||
| 模块 | 输入 | 输出 |
|
||
| --- | --- | --- |
|
||
| `BRepAnalyzer` | B-Rep、Config、KernelContext | descriptors、SA、EA、AA、support groups |
|
||
| `CandidateEnumerator` | analysis、Config | finite primitive candidates |
|
||
| `CandidateScorer` | candidate、current residual analysis | bitsets、coverage、LocalScore |
|
||
| `ResidualEngine` | residual、candidate、KernelContext | sorted Rplus/Rminus components |
|
||
| `ProgramSearch` | root residual、Config | finite completed programs |
|
||
| `ProgramValidator` | program、target atoms、Config | validation metrics、atom owners |
|
||
|
||
## 27. 测试要求
|
||
|
||
### 27.1 确定性
|
||
|
||
对相同 STEP bytes、backend version 和 config 重复运行两次，以下 bytes 必须相同：
|
||
|
||
- atom records canonical JSON。
|
||
- event records canonical JSON。
|
||
- CandidateKey 序列。
|
||
- ProgramKey。
|
||
- 非 timeout 情况下的最终 ExplanationResult canonical JSON；运行时间字段除外。
|
||
|
||
### 27.2 单 primitive
|
||
|
||
对 Box、Cylinder、Cone、Sphere 和 ring Torus fixture：
|
||
|
||
```text
|
||
ValidExplanation(expected_primitive_program, fixture) == true
|
||
ProgramCost(expected_primitive_program) < RawBRepCost(fixture)
|
||
```
|
||
|
||
### 27.3 Boolean
|
||
|
||
对 Box 减 Cylinder、Box 加 Cylinder、同轴 Cylinder 相减 fixture：
|
||
|
||
- 返回 `VALID_EXPLANATION`。
|
||
- `symdiff_volume <= eps_volume`。
|
||
- `max_boundary_distance <= eps_surface`。
|
||
- `max_normal_error <= eps_normal`。
|
||
- `owned_surface_atom_count == surface_atom_count`。
|
||
|
||
### 27.4 Face split
|
||
|
||
对几何相同但 Face split 不同的两个 STEP：
|
||
|
||
- 最优程序的 `ProgramKey` 相同。
|
||
- 最优程序的 `ProgramCost` 相同。
|
||
- 两者各自 `ValidExplanation == true`。
|
||
|
||
不比较 atom 数量，因为三角化可能跟随输入 Face split 变化。
|
||
|
||
### 27.5 NURBS
|
||
|
||
- 可约化 NURBS Cylinder：`RecognizeAnalytic` 返回完整 Cylinder 参数且通过采样验证。
|
||
- exact-key 相同的 NURBS Face：产生同一个 exact group。
|
||
- pairwise sampled match 不取传递闭包。
|
||
- 全自由曲面 closed solid：在预算内返回 `RawBRep` 或包含 RawBRep residual 的有效程序。
|
||
|
||
### 27.6 硬预算
|
||
|
||
每次测试断言：
|
||
|
||
```text
|
||
search_boolean_calls <= max_search_boolean_calls
|
||
search_total_kernel_calls <= max_search_total_kernel_calls
|
||
expanded_states <= max_expanded_states
|
||
each_task_depth <= max_task_depth
|
||
validation_boolean_calls <= max_validation_boolean_calls
|
||
validation_total_kernel_calls <= max_validation_total_kernel_calls
|
||
```
|
||
|
||
## 28. 算法总流程
|
||
|
||
```text
|
||
STEP B-Rep
|
||
|
|
||
v
|
||
解析并验证 Config
|
||
|
|
||
v
|
||
ValidSolid + 固定参数三角化/边离散
|
||
|
|
||
v
|
||
构造有限 SA / EA / AA 和 support groups
|
||
|
|
||
v
|
||
从有限 Direction/Position/Axial/Extent 事件枚举 primitive candidates
|
||
|
|
||
v
|
||
计算 explanation bitsets、coverage 和 LocalScore
|
||
|
|
||
v
|
||
Top-M 候选计算 R+ 与 R-
|
||
|
|
||
v
|
||
ExpansionEstimate 门槛
|
||
|
|
||
v
|
||
固定模板替换规则 + 有界 Beam Search
|
||
| \
|
||
| +--> 每个 Slot 无条件可替换为 RawBRep
|
||
v
|
||
有限个完成 Program
|
||
|
|
||
v
|
||
Render + symmetric difference + 双向边界/法向 + topology signature
|
||
|
|
||
v
|
||
SurfaceAtom polarity owner
|
||
|
|
||
v
|
||
在 ValidExplanation 集合中最小化 ProgramCost
|
||
```
|
||
|
||
## 29. 结论
|
||
|
||
v0.2 将原始设想翻译为以下有限优化问题。给定输入 `T`、固定配置 `C` 和搜索实际枚举到的有限程序集合 `Programs(T,C)`：
|
||
|
||
\[
|
||
P^*=argmin_{P\in Programs(T,C)} ProgramCost(P)
|
||
\]
|
||
|
||
约束：
|
||
|
||
\[
|
||
ValidExplanation(P,T)=true
|
||
\]
|
||
|
||
基础单元常见性由 `PrimitiveCost`、`NurbsCost` 和 `RawBRepCost` 表示；解释多少边和面由 `CandidateExplanation` bitset 及加权覆盖率表示；“基础几何元素 + 剩余部分”由两个 regularized cut 和第 15.3 节固定程序模板表示；递归由有限事件、候选上限、Beam Width、任务深度、状态数、kernel 调用数、Boolean 调用数和 deadline 限制。
|
||
|
||
因此该规范不需要枚举任意空间中的全部几何体，也不需要对一般 NURBS 求不可控的全局拟合；在所有搜索路径失败或预算耗尽时，`RawBRep` 分支给出有限、可重放的兜底程序。
|