1. Luồng B-rep (B-rep Streams)
Rõ ràng cần thiết lập quy trình sản xuất (producer process) nhập B-rep, được định nghĩa bên ngoài bởi định dạng đa giác chuẩn (ví dụ: wavefront hoặc file java3D obj), vào luồng đầu vào cho đường ống hình học (geometric pipeline) của chúng ta. Biểu diễn biên (boundary representation) do đa giác và vector pháp tuyến cung cấp phải được định hướng liên tục (coherently oriented). Việc lọc file đầu vào để xử lý đa giác không phẳng và các sai số hình học khác có thể cần thiết cho các mô hình hình học lưu trữ chung chủ yếu dùng trong đồ họa máy tính. Luồng đầu ra của các tam giác được định hướng liên tục, sau đó được chuyển đổi thành cây BSP (Binary Space Partitioning) tiến bộ song song (twin progressive-BSP) bởi các bước thuật toán mô tả dưới đây.
2. Phác thảo thuật toán B-rep sang BSP
Thủ tục cơ bản của phương pháp chúng ta là tính toán quán tính (inertia) của các tập hợp tam giác bằng cách co quán tính đã tính trước của từng tam giác, và phân rã Eigen (Eigen decomposition) của quán tính tập hợp tam giác để giới hạn hình dạng của chúng một cách tối ưu và đệ quy.
Trong trường hợp d chiều, giới hạn hình dạng được đạt được bằng cách sử dụng 2 siêu phẳng tiếp cực trị (extremal tangent hyperplanes) cho mỗi trong d eigenvector của ma trận Euler. Giao điểm của 2d siêu không gian tương ứng tạo ra hình bình hành (hyper)parallelepiped phù hợp nhất (best-fitting) của tập hợp biên chứa trong ô hiện tại. Ở 3 chiều, có 6 = 2×3 mặt phẳng như vậy.
Khởi tạo (Initialization)
- Tenxơ Euler mở rộng affine (affinely extended Euler tensors) của mỗi tam giác đầu vào được tính trước (theo thời gian tuyến tính).
- Toàn bộ tập tam giác đầu vào được gán cho gốc BSP.
- Toàn bộ không gian E3 (là lồi) được gán cho gốc.
- Nhãn gốc đặt là FUZZY.
Trường hợp đệ quy (Recursive case)
- Ô FUZZY hiện tại được chia bởi tối đa 6 siêu phẳng trực giao vuông góc với eigenvector của biểu diễn ma trận tenxơ Euler của tập hợp tam giác hiện tại.
- Các mặt phẳng này được tính qua giá trị nhỏ nhất và lớn nhất của hàm tuyến tính w = a · v được đánh giá trên các đỉnh v của tập hợp tam giác hiện tại, trong đó a là eigenvector hiện tại.
- Đối với mỗi eigenvector, tối đa 3 ô lồi được tạo ra bởi hai siêu phẳng song song max-min, là {OUT, FUZZY, IN} hoặc {OUT, FUZZY, OUT}.
- Mỗi ô FUZZY được chia tiếp bởi siêu phẳng chính (principal hyper-plane) liên quan đến eigenvector lớn nhất.
- Một tập hợp tam giác nhỏ hơn được gán cho mỗi ô đã chia qua kiểm tra chứa đựng đỉnh của chúng.
- Các tam giác cắt mặt phẳng chia bị chia tách, và các (phần) tam giác được gán cho cây con nút.
Trường hợp cơ bản (Base case)
Chia đệ quy dựa trên quán tính dừng khi ô hiện tại chỉ chứa số lượng nhỏ tam giác biên. Một phép chia ô cuối cùng được thực hiện bằng các mặt phẳng của các tam giác biên.