Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement short-circuit volume evaluation using infix notation #1282

Open
sethrj opened this issue Jun 18, 2024 · 1 comment
Open

Implement short-circuit volume evaluation using infix notation #1282

sethrj opened this issue Jun 18, 2024 · 1 comment
Assignees
Labels
orange Work on ORANGE geometry engine performance Changes for performance optimization

Comments

@sethrj
Copy link
Member

sethrj commented Jun 18, 2024

Based off some still unpublished but available research by @paulromano et al., there could be substantial savings in the way that we evaluate point-in-volume for initialization and surface crossing in ORANGE. (It's also used for distance-to-boundary for "complex" and "background" volumes since internal surface crossings have to be evaluated.)

I think we can break it down into the following steps:

  1. Develop an on-device InfixEvaluator that applies a function f(literal) -> bool (where literal usually means a surface index possibly with negation) and returns the evaulated result, using short circuit logic. (Implement infix evaluator #1286)
  2. Add a CSG "simplifier" that replaces negated joins with the opposite kind of join using DeMorgan's laws. (Implement operation to simplify negated join on CsgTree #1289)
  3. Add a utility to generate infix notation from the simplified tree (Support building infix logic representation #1530)
  4. Add a utility to import from postfix notation (external JSON) to CSG tree for SCALE compatibility (@sethrj )
  5. Pass an infix logic representation rather than prefix through the OrangeInput into the params data

After using the infix evalutor and comparing performance, then we can replace the "precalculate surface senses" operation with "on-the-fly surface senses". (#1539)

@sethrj sethrj added orange Work on ORANGE geometry engine performance Changes for performance optimization labels Jun 18, 2024
@sethrj
Copy link
Member Author

sethrj commented Jun 18, 2024

Question for @paulromano : on-the-fly sense evaluation works for "point in volume" but might be difficult for "distance to boundary" in the case with internal surface crossings. To do that right now, we precalculate all the surfaces with the starting point, progressively move through nearest surfaces, flip the senses as we cross them, and evaluate "inside" at each one of those points. For the internal surface case, do you re-evaluate at every internal surface crossing? (I guess we could probably cache just a single surface state rather than all of them...?)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
orange Work on ORANGE geometry engine performance Changes for performance optimization
Projects
None yet
Development

No branches or pull requests

2 participants