chenzhaiyu / abspy

A Python tool for 3D adaptive binary space partitioning and beyond
https://abspy.readthedocs.io/
MIT License
66 stars 10 forks source link

Add additional intersection test with OBB and SAT #20

Closed wangyuqing0424 closed 9 months ago

wangyuqing0424 commented 10 months ago

This PR adds an additional set of intersection tests between primitive and cells using SAT, on top of the existing AABB test. The intersection tests reduce the runtime and the number of resulting cells.

chenzhaiyu commented 10 months ago

@wangyuqing0424 Thanks! Would the pre-intersection test work faster if you cache target variables as many as possible instead of computing them ad-hoc each time? Please also briefly mention the idea by editing the comment above so people know what we're hacking here :)

wangyuqing0424 commented 9 months ago

The attempt to optimize runtime speed through caching target variables has not yielded significant improvements, as the computation of target variables does not take much processing time

wangyuqing0424 commented 9 months ago
  1. Leveraging the Separating Axis Theorem (SAT), we conducted one further test to determine whether oriented bounding boxes (OBBs) of cells and primitives intersect along the axes defined in SAT.
  2. By incorporating an additional intersection test in the test_combined , we were able to reduce the number of cells from 78 to 62, resulting in a runtime improvement from 1.40s to 1.38s. In the test_complex , we were able to reduce the number of cells from 789 to 737, resulting in a runtime improvement from 19.18s to 17.60s.
chenzhaiyu commented 9 months ago

Tested working on the complex test_church.obj data. Stats below recorded with AMD EPYC 7542 a single core: