Feature Request: Find Data/Filter to Identify/Quantify Overlapping Elements

As far as a "Find Data" capability goes, I think it almost exists. I get an error when attempting this, but in the Find Data tool you can submit a query like the following:

I would expect this query to result in a selection of points that are in both Block 1 and Block 2. You could do the same query for cells. Unfortunately it looks like the code is not expecting a query like this, since I get the error:

Error: Failed to evaluate Expression '(contains(,[1]))'. The following exception stack should provide additional developer specific information. This typically implies a malformed expression. Verify that the expression is valid.

Warning: In /Users/kitware/dashboards/buildbot-slave/a64f5607/build/superbuild/paraview/src/VTKExtensions/ExtractionPython/vtkPythonSelector.cxx, line 76
vtkPythonSelector (0x600009131540): Could not invoke 'python_selector.execute()'

Traceback (most recent call last):
  File "/Applications/ParaView-5.8.0.app/Contents/Python/paraview/detail/python_selector.py", line 79, in execute
    maskArray = calculator.compute(inputs, query, ns=elocals)
  File "/Applications/ParaView-5.8.0.app/Contents/Python/paraview/detail/calculator.py", line 146, in compute
    retVal = eval(subEx, globals(), mylocals)
  File "<string>", line 1
    (contains(,[1]))
              ^
SyntaxError: invalid syntax

@jkulesza_lanl If this query worked, would it be good enough to resolve the Find Data portion of this issue?

If this query worked, would it be good enough to resolve the Find Data portion of this issue?

Maybe. A couple questions to help turn that to 'yes':

What happens if I have dozens/hundreds of blocks and I want to detect overlaps between any elements in any combination of those blocks?
For the cell-based query, for quadratic elements, face curvature might lead to overlaps that linear faces, linear edges, mid-edge nodes, and vertices wouldn't report. Would this be handled?

What happens if I have dozens/hundreds of blocks and I want to detect overlaps between any elements in any combination of those blocks?

If the goal is to detect any overlapping elements throughout all of the blocks, then Find Data would not be sufficient. As it is now, you would need to specify which blocks to query.

For the cell-based query, for quadratic elements, face curvature might lead to overlaps that linear faces, linear edges, mid-edge nodes, and vertices wouldn't report. Would this be handled?

I don't know enough to have an answer.

If the goal is to detect any overlapping elements throughout all of the blocks

That is the goal. I'd like to be able to identify any and all overlaps in the entire model.

I don't know enough to have an answer.

That's fair. These are concerns that get into the algorithms used. Perhaps as a ParaView developer is working through correcting Find Data to permit the technique you proposed, they can provide insight into these other geometric considerations.

added project:lanl label

added priority:important label

changed milestone to %5.9 (Fall 2020)

Let's start by thinking of this as a filter. We can see if it makes sense to expose this via find-data once we've identified what we need this filter to do.

Do you need to know which cell(s) a particular cell intersects with or just the flag indicating there's an overlap?

A flag is probably sufficient, because (a) it's not clear to me how we'd use the identifying information for overlaps and (b) once we know that there are overlaps, we can then query in to learn more about those overlapping cells.

With respect to the flag: I would prefer an integer assigned to a given cell indicating how many other cells it overlaps with (thus, 0 is that there are no overlaps). This will then permit interrogating which cells are most-poorly defined to then focus attention. This might act alongside the suggestion in the original ticket:

Ideally, one could also quantify the degree of overlap by calculating the fraction of volume of a given element that is shared with overlapping elements.

sounds good. Do you have a sample dataset to use as a model to build the solution?

See attached for 3 components with different materials within a single block with varying degrees of overlap. All parts are identical with 24 first-order tetrahedra each (total 72 tetrahedra).

Another reasonable and valid test case is separating these three cubes into three separate, overlapping, blocks.

Screenshot

Sample File

test.abaq.eeout.vtu

do we care about the material ids at all ? Is overlap between cells with the same material id acceptable?

No, I just used that as a way to distinguish regions. Any form of overlap should be registered (i.e., no overlaps are "acceptable").

Cool, sounds good. Thanks!

assigned to @yohann.bearzi

What do you guys mean by "a flag"? Like a warning in the console?

A filter doing that intersection check could be a filter whose output are the intersecting cells, i.e. a "good" dataset would be one that produces no output.

I have a code in a ParaView plugin that computes the intersection volume between a box and any polyhedron without actually creating the intersected polyhedron (saves a lot of time). It could be generalized for any couple of polyhedrons, but the algorithm might take a while to write with 100% accuracy. It was already very difficult for the box / polyhedron case.

A cell could have zones that are intersected by multiple cells. If you want to know the intersection volume, do you want the sum of all intersection volumes, i.e. potentially a volume larger than the cell's volume, or do you want the true overall intersection volume?

What do you guys mean by "a flag"? Like a warning in the console?

no; a flag means adding an output int array which for each cell contains a count for number of other cells that cell overlaps. 0 mean it doesn't overlap any other cell.

A cell could have zones that are intersected by multiple cells. If you want to know the intersection volume, do you want the sum of all intersection volumes, i.e. potentially a volume larger than the cell's volume, or do you want the true overall intersection volume?

don't think we need to compute the actual intersection here to begin with; we just need to know if the cells overlap.

mentioned in merge request vtk/vtk!6789 (merged)

mentioned in commit yohann.bearzi/vtk@8e73000f

mentioned in commit yohann.bearzi/vtk@911c9544

mentioned in commit yohann.bearzi/vtk@a7fbe8fa

mentioned in commit yohann.bearzi/vtk@c9b26438

mentioned in commit yohann.bearzi/vtk@1fa1cc71

mentioned in commit yohann.bearzi/vtk@72c8353d

mentioned in commit yohann.bearzi/vtk@52265d21

mentioned in commit yohann.bearzi/vtk@1498b8a8

mentioned in commit yohann.bearzi/vtk@a5d7544a

mentioned in commit yohann.bearzi/vtk@6f88241d

mentioned in commit yohann.bearzi/vtk@d416f4c0

mentioned in commit yohann.bearzi/vtk@6131f174

mentioned in commit yohann.bearzi/vtk@6a81f6dd

mentioned in merge request vtk/vtk!6909 (merged)

mentioned in merge request !4149 (merged)

closed via merge request !4149 (merged)

closed via commit e153f5f3

added workflow:needs-verification label

What is a good way to test this---would tonight's nightly contain this work?

I think it should.

The name of the filter is Overlapping Cells Detector in ParaView. It takes any vtkPointSet input so far.

Excellent, thanks. I'll pull down the nightly tomorrow and will exercise this. Thanks for your work on this!

@yohann.bearzi, FYI, some testing results from the May 30 nightly:

The dataset produced as a result of applying this filter is named "NumberOfCollisionsPerCell". The relationship of this name to the filter applied is not evident; can the dataset-filter naming be made consistent?
I tested this filter for an XDMF+HDF5 two-block linear hexahedron model with 800 elements (cells). Processing has taken over one minute, so far, and has not finished. I tried merging the blocks and this did not improve the time. Would this level of performance be expected? Further, see final point about correctness.
Note that testing with the same model using linear tetrahedra (still XDMF+HDF5) operates almost instantly (as expected).
Testing with ~1.5 million linear tetrahedral XDMF+HDF5 model (~900 blocks) took ~30 seconds to process. This level of performance seems reasonable to me.
I tested with identical non-overlapping models from here, one created with linear tetrahedra (lintet) and one created with linear hexahedra (linhex). The lintet model shows the correct number of overlaps everywhere (0), but the linhex model shows varying numbers of overlaps. This is incorrect. Screenshots follow.

Materials

Correct (lintet)

Incorrect (linhex)

reopened

removed workflow:needs-verification label

Thanks for testing this filter. I can change the name of the scalar field in a follow up merge request.

I'll also look at what happens with the hexahedra. The collision detection relies on already existing polymorphic methods, so maybe the hexahedron behaves slightly differently than the other cells regarding numeric precisions. I'll try to reproduce this bug on another dataset with hexahedra in it, and see what is going on.

Regarding the performance issue you encountered with your 2-block dataset, can you share the dataset so I can look at what is happening? Did you run it in a multi-process environment or in a single process one? The filter has a complexity of O(n log (n)), where n is the number of input cells, so it is not normal for it taking that long for 800 cells.

Regarding the performance issue you encountered with your 2-block dataset, can you share the dataset so I can look at what is happening? Did you run it in a multi-process environment or in a single process one? The filter has a complexity of O(n log (n)), where n is the number of input cells, so it is not normal for it taking that long for 800 cells.

Sorry for the slow reply. The dataset is attached. I've included it in as a 2-block XDMF+HDF5 and a single-block VTU. Performance is unexpectedly slow in both cases.

I ran on the nightly indicated using a standard execution on macOS. So, I think, single-process execution (i.e., Auto MPI is not enabled). I ran identically to how I ran the tetrahedral models, which took a reasonable amount of time relative to their complexity.

linhex.zip

mentioned in commit yohann.bearzi/vtk@62dceae9

mentioned in merge request vtk/vtk!6969 (merged)

mentioned in commit yohann.bearzi/vtk@c40ab13c

mentioned in commit yohann.bearzi/vtk@da464169

mentioned in commit yohann.bearzi/vtk@c76c0a84

mentioned in commit yohann.bearzi/vtk@a32d053f

mentioned in commit yohann.bearzi/vtk@9207d89a

mentioned in commit yohann.bearzi/vtk@8b58a6bc

mentioned in commit yohann.bearzi/vtk@5a8cacbc

mentioned in commit yohann.bearzi/vtk@5261a8f2

@yohann.bearzi I'm excited to see work continuing on this with your recent VTK commits. Please let me know when the next nightly is ready for more testing. Thank you!

It's coming soon. I needed a slightly more fancy matrix multiplication utility that I upgraded and merged last week. This filter should be good to go by the beginning of next week.