Archived issue #0023200
Visualization - prevent multiple triangulating of a shape that already has been triangulated
Description
When the AIS_InteractiveContext processes a shaded shape (e.g. Displaying) it checks whether the triangulation of the shape exists. This is performed in
StdPrs_ShadedShape::Add, line 274 using the BRepTools::Triangulation method.
There are three reasons (see BRepTools::Triangulation) why this function decides there is no valid triangulation. Those cases are:
- Poly_Triangulation is Null for a face of the checked shape
- the deflection of the Poly_Triangulation of a face is greater than the provided one
- Poly_PolygonOnTriangulation is Null for one edge of the checked shape
If one of the above occurs the triangulation of the shape is re-computed.
However, since the re-computation does not guarantee that the above conditions are met this might result in a repetitive re-computing of a shape triangulation.
This effect can be observed when displaying and then redisplaying again large models.
StdPrs_ShadedShape::Add, line 274 using the BRepTools::Triangulation method.
There are three reasons (see BRepTools::Triangulation) why this function decides there is no valid triangulation. Those cases are:
- Poly_Triangulation is Null for a face of the checked shape
- the deflection of the Poly_Triangulation of a face is greater than the provided one
- Poly_PolygonOnTriangulation is Null for one edge of the checked shape
If one of the above occurs the triangulation of the shape is re-computed.
However, since the re-computation does not guarantee that the above conditions are met this might result in a repetitive re-computing of a shape triangulation.
This effect can be observed when displaying and then redisplaying again large models.
Steps to reproduce
AIS_InteractiveContext::SetDeviationCoefficient(0.0001)
Load the attached model.
AIS_InteractiveContext::Display
AIS_InteractiveContext::Redisplay
As the deflection criterion is not met the shape will be triangulated twice.
Load the attached model.
AIS_InteractiveContext::Display
AIS_InteractiveContext::Redisplay
As the deflection criterion is not met the shape will be triangulated twice.
Additional information
New flag IsAutoTriangulated was added to Prs3d_Drawer. It is True by default.
If this flag is True automatic re-triangulation with deflection-check logic will be applied (previous behavior).
Else this feature will be disable and triangulation is expected to be computed by application itself.
Special wireframe presentation (with more U and V isoparametric curves) for faces without triangulation was added.
Syntax of "vdefalts" command was changed and new parameter -autoTriang was added for check of new AutoTriangulated functionality. Now it looks like this:
vdefaults [-absDefl value] [-devCoeff value] [-angDefl value] [-autoTriang {off/on | 0/1}]
If this flag is True automatic re-triangulation with deflection-check logic will be applied (previous behavior).
Else this feature will be disable and triangulation is expected to be computed by application itself.
Special wireframe presentation (with more U and V isoparametric curves) for faces without triangulation was added.
Syntax of "vdefalts" command was changed and new parameter -autoTriang was added for check of new AutoTriangulated functionality. Now it looks like this:
vdefaults [-absDefl value] [-devCoeff value] [-angDefl value] [-autoTriang {off/on | 0/1}]
Public activity
33 archived notes
Participants are labeled by their role within this record.
Just an observation: Methods like:
XCAFPrs_AISObject::SetMaterial
XCAFPrs_AISObject::SetColor
XCAFPrs_AISObject::SetTransparency
force the recomputation of the presentation for the corresponding XCAFPrs_AISObject which leads to the recomputation of the triangulation of an object under the conditions mentioned above.
XCAFPrs_AISObject::SetMaterial
XCAFPrs_AISObject::SetColor
XCAFPrs_AISObject::SetTransparency
force the recomputation of the presentation for the corresponding XCAFPrs_AISObject which leads to the recomputation of the triangulation of an object under the conditions mentioned above.
I have pushed the branch CR23200 onto the server. I do not mark the issue as solved, though.
The committed change only comments out the code portion responsible for repetitive triangulation calls (this happens especially when using XDE). Additionally, I had to make sure that within our application the triangulation is generated/updated each time a shape is created/changed.
So this is rather a workaround than a solution but it might be interesting for those willing to optimize the performance in their XDE-based application.
The committed change only comments out the code portion responsible for repetitive triangulation calls (this happens especially when using XDE). Additionally, I had to make sure that within our application the triangulation is generated/updated each time a shape is created/changed.
So this is rather a workaround than a solution but it might be interesting for those willing to optimize the performance in their XDE-based application.
Author brings a valid concern and this is a case that sometimes happens indeed. OCC should foresee the way to avoid re-triangulating the face if a previous attempt with exact same input parameters failed.
My guess is that introducing an extra Standard_Real field into BRep_TFace, named something like myUsedDeflection or alike would address this issue. A value of <=0. would mean that no attempts have been made yet, while a positive value would store a value used in a previously attempt.
BRepMesh would compare a cached value against its input parameter and would skip the face if myUsedDeflection is less than or equal to that parameter.
This would add 8 bytes * Number_of_faces extra memory footprint but this should hopefully be acceptable.
Perhaps, myLocation could be removed from the BRep_TFace as locations are attached to TopoDS_Shapes anyway. This would save at least 4 or 8 bytes depending on the architecture.
My guess is that introducing an extra Standard_Real field into BRep_TFace, named something like myUsedDeflection or alike would address this issue. A value of <=0. would mean that no attempts have been made yet, while a positive value would store a value used in a previously attempt.
BRepMesh would compare a cached value against its input parameter and would skip the face if myUsedDeflection is less than or equal to that parameter.
This would add 8 bytes * Number_of_faces extra memory footprint but this should hopefully be acceptable.
Perhaps, myLocation could be removed from the BRep_TFace as locations are attached to TopoDS_Shapes anyway. This would save at least 4 or 8 bytes depending on the architecture.
Yes that's pretty logical, just Poly_Triangulation is better candidate for adding this field.
Not quite. Poly_Triangulation can be null if the triangulation failed. So the value has to be stored upstream - that's why BRep_TFace has been suggested.
Well, to tell the truth this issue is really critical in my opinion.
We use XDE to handle complete car bodies in our application. It takes ages in that case to just change a color of a face/shape because the triangulation for the whole assembly has to be recomputed.
We use XDE to handle complete car bodies in our application. It takes ages in that case to just change a color of a face/shape because the triangulation for the whole assembly has to be recomputed.
A side note. Prior to version 6.5.2 it was possible to avoid re-computation: Prs3d_ShadedShape::Add() always invoked an algorithm registered in BRepMesh_DiscretFactory. One could register a void algorithm (a subclass of BRepMesh_DiscretRoot with empty Perform() implementation) and thus no re-computation took place. Actual triangulation took place prior to visualization. This was an approach used by CAD Exchanger, for example.
As of version 6.5.2 the Prs3d_ShadedShape (which then moved to StdPrs_ShadedShape) there is an attempt to avoid re-triangulation by checking with BRepTools::Triangulation(). However in the case when already computed triangulation is more coarse than requested, it now enforces cleanup (BRepTools::Clean()) and tries to recompute. Very often this will repeatedly fail, as initial requested deflection was likely the same as current and the algorithm already failed to respect it.
Thus, in some cases (which are typically more difficult for the mesher) this optimization turns out to be a regression. The bad news is that now there is no work-around against this and one cannot avoid recomputation at all. So a fix is definitively welcome.
As of version 6.5.2 the Prs3d_ShadedShape (which then moved to StdPrs_ShadedShape) there is an attempt to avoid re-triangulation by checking with BRepTools::Triangulation(). However in the case when already computed triangulation is more coarse than requested, it now enforces cleanup (BRepTools::Clean()) and tries to recompute. Very often this will repeatedly fail, as initial requested deflection was likely the same as current and the algorithm already failed to respect it.
Thus, in some cases (which are typically more difficult for the mesher) this optimization turns out to be a regression. The bad news is that now there is no work-around against this and one cannot avoid recomputation at all. So a fix is definitively welcome.
Dear Roman,
thanks for supporting the idea!
thanks for supporting the idea!
For the XDE-based apps the negative effect of this optimization attempt (check of BRepTools::Triangulation()) is even worse.
Imagine, one has precomputed a triangulation for the entire shape S and then displays with the help of XDE (XCAFPrs_AISObject). XCAFPrs_AISObject::Compute() classifies subshapes into groups with the same attributes. A bounding box (and hence computed deflection) for each of this subshape will be less than of an entire S, so Prs3d_ShadedShape will clean up the triangulation of each group and recompute. Moreover, the polygonization of the edge shared by two faces from two different groups can be cleaned up and hence will invalidate one group. The latter will clean up all the edges inside that group and hence will propagate to the entire S. This will repeat over and over again, with every display, as deflection computed and successfully respected for a group k may be not enough for some further group k+s.
Perhaps, this is what Author is observing on his large assemblies.
Thinking about a possible fix, I tend to think that the verification algorithm should be user-parametrized. In some cases, it should be strict and clean up the triangulation if at least one face does not meet it. In other cases, when a developer is certain that if the triangulation is in place then it is good and it is enough to find at least one face with triangulation than to scan 100+K faces.
To achieve that the following options are possible:
1. The easiest would be to roll back to pre-6.5.2 behavior and let decision-making be a part of user-defined subclass of BRepMesh_DiscretRoot::Perform().
2. Extend BRepMesh_DiscretRoot API to explicitly support decision-making
With #0000002, Prs3d_ShadedShape would look like:
Handle(BRepMesh_DiscretRoot) aMeshAlgo = BRepMesh_DiscretFactory::Get().Discret (theShape,
aDeflection,
theDrawer->HLRAngle());
if (!aMeshAlgo.IsNull() && !aMeshAlgo->AcceptTriangulation (theShape, aDeflection)) {
BRepTools::Clean (theShape);
aMeshAlgo->Perform();
}
Default implementation of AcceptTriangulation() could call BRepTools::Triangulation() as now. XDE-based apps would have to take care to redefine this root and prebuild triangulation in advance. Not a silver bullet but still more efficient than current 6.6.0.
Imagine, one has precomputed a triangulation for the entire shape S and then displays with the help of XDE (XCAFPrs_AISObject). XCAFPrs_AISObject::Compute() classifies subshapes into groups with the same attributes. A bounding box (and hence computed deflection) for each of this subshape will be less than of an entire S, so Prs3d_ShadedShape will clean up the triangulation of each group and recompute. Moreover, the polygonization of the edge shared by two faces from two different groups can be cleaned up and hence will invalidate one group. The latter will clean up all the edges inside that group and hence will propagate to the entire S. This will repeat over and over again, with every display, as deflection computed and successfully respected for a group k may be not enough for some further group k+s.
Perhaps, this is what Author is observing on his large assemblies.
Thinking about a possible fix, I tend to think that the verification algorithm should be user-parametrized. In some cases, it should be strict and clean up the triangulation if at least one face does not meet it. In other cases, when a developer is certain that if the triangulation is in place then it is good and it is enough to find at least one face with triangulation than to scan 100+K faces.
To achieve that the following options are possible:
1. The easiest would be to roll back to pre-6.5.2 behavior and let decision-making be a part of user-defined subclass of BRepMesh_DiscretRoot::Perform().
2. Extend BRepMesh_DiscretRoot API to explicitly support decision-making
With #0000002, Prs3d_ShadedShape would look like:
Handle(BRepMesh_DiscretRoot) aMeshAlgo = BRepMesh_DiscretFactory::Get().Discret (theShape,
aDeflection,
theDrawer->HLRAngle());
if (!aMeshAlgo.IsNull() && !aMeshAlgo->AcceptTriangulation (theShape, aDeflection)) {
BRepTools::Clean (theShape);
aMeshAlgo->Perform();
}
Default implementation of AcceptTriangulation() could call BRepTools::Triangulation() as now. XDE-based apps would have to take care to redefine this root and prebuild triangulation in advance. Not a silver bullet but still more efficient than current 6.6.0.
Dear Author,
Can you please check if the patch from Git branch CR25142 resolves the issue?
My feeling is that now it should work as expected, as the triangulation is no longer cleaned if BRepTools::Triangulation() returns Standard_False.
Can you please check if the patch from Git branch CR25142 resolves the issue?
My feeling is that now it should work as expected, as the triangulation is no longer cleaned if BRepTools::Triangulation() returns Standard_False.
Dear Sergey,
unfortunately I cannot confirm fixing this issue.
One problem still remains: When the deflection of the existing Poly_Triangulation of a face is greater than the provided one re-computation is still forced.
If the (re)computation fails to create a triangulation with the desired deflection it will be triggered again and again.
unfortunately I cannot confirm fixing this issue.
One problem still remains: When the deflection of the existing Poly_Triangulation of a face is greater than the provided one re-computation is still forced.
If the (re)computation fails to create a triangulation with the desired deflection it will be triggered again and again.
Dear Author,
I have tried the following simple test with the shape attached to this issue:
So I do not see any problems with the current Git master.
Thus can you please attach a shape that could be used to reproduce the problem described by you - i.e. when BRepMesh fails to create a tessellation with requested deflection and so re-triangulates the shape each time.
Or please formulate the remaining problem(s) precisely, with relevant test case(s).
We need to understand clearly what should be corrected, otherwise we cannot proceed with this issue.
Thanks in advance!
[signature removed]
Sergey
I have tried the following simple test with the shape attached to this issue:
pload ALL restore Attachment 1 (BREP) s vinit vsetdispmode 1 vdisplay s vfit trinfo s # Max deflection = 0.087 # Using 10x less deflection incmesh s 0.01 trinfo s # Max deflection = 0.0071 # Attach to DRAWEXE with a debugger and set a # breakpoint in StdPrs_ShadedShape::Tessellate() vdisplay s # BRepTools::Triangulation (theShape, aDeflection) returns True -> # triangulation is not redone!
So I do not see any problems with the current Git master.
Thus can you please attach a shape that could be used to reproduce the problem described by you - i.e. when BRepMesh fails to create a tessellation with requested deflection and so re-triangulates the shape each time.
Or please formulate the remaining problem(s) precisely, with relevant test case(s).
We need to understand clearly what should be corrected, otherwise we cannot proceed with this issue.
Thanks in advance!
[signature removed]
Sergey
Dear Sergey,
I have uploaded a file to demonstrate the problem.
Running the script in DRAW shows that meshing does not result in the given deflection and so the shape might be re-meshed over and over.
trinfo s
#This shape contains 25559 triangles.
# 17138 nodes.
#Maximal deflection 0.26360344286498899
incmesh s 0.026
#Incremental Mesh, multi-threading OFF
#Meshing statuses: NoError
trinfo s
#This shape contains 47189 triangles.
# 28002 nodes.
#Maximal deflection 0.051743440306355422
I have uploaded a file to demonstrate the problem.
Running the script in DRAW shows that meshing does not result in the given deflection and so the shape might be re-meshed over and over.
trinfo s
#This shape contains 25559 triangles.
# 17138 nodes.
#Maximal deflection 0.26360344286498899
incmesh s 0.026
#Incremental Mesh, multi-threading OFF
#Meshing statuses: NoError
trinfo s
#This shape contains 47189 triangles.
# 28002 nodes.
#Maximal deflection 0.051743440306355422
It is suggested to introduce new flag in Drawer to perform or not automatic triangulation.
By default, this flag would be set ON to preserve current behavior - automatic re-triangulation with messy deflection-check logic (which might be improved in future).
New applications would better switch this flag OFF to disable feature. In this case triangulation is expected to be computed by application itself (and NO shading presentation at all if unavailable).
By default, this flag would be set ON to preserve current behavior - automatic re-triangulation with messy deflection-check logic (which might be improved in future).
New applications would better switch this flag OFF to disable feature. In this case triangulation is expected to be computed by application itself (and NO shading presentation at all if unavailable).
Sounds reasonable. Thank you.
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: osa
Date: Fri Feb 13 10:17:19 2015 +0300
0023200: Visualization - multiple triangulating of a shape that already has been triangulated
[revision removed]
Detailed log of new commits:
Author: osa
Date: Fri Feb 13 10:17:19 2015 +0300
0023200: Visualization - multiple triangulating of a shape that already has been triangulated
Dear Kirill,
the patch is ready (branch CR23200_1). Please review.
the patch is ready (branch CR23200_1). Please review.
Please extend description of the patch in the commit.
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: osa
Date: Fri Feb 13 12:22:14 2015 +0300
0023200: Visualization - prevent multiple triangulating of a shape that already has been triangulated
Add new flag IsAutoTriangulated to Prs3d_Drawer. It is True by default.
If this flag is True automatic re-triangulation with deflection-check logic will be applied.
Else this feature will be disable and triangulation is expected to be computed by application itself.
Change the syntax of vdefalts command.
Add new parameter -autoTriang for check of AutoTriangulated functionality.
[revision removed]
Detailed log of new commits:
Author: osa
Date: Fri Feb 13 12:22:14 2015 +0300
0023200: Visualization - prevent multiple triangulating of a shape that already has been triangulated
Add new flag IsAutoTriangulated to Prs3d_Drawer. It is True by default.
If this flag is True automatic re-triangulation with deflection-check logic will be applied.
Else this feature will be disable and triangulation is expected to be computed by application itself.
Change the syntax of vdefalts command.
Add new parameter -autoTriang for check of AutoTriangulated functionality.
Dear Kirill,
the patch was updated (branch CR23200_2). Please review.
the patch was updated (branch CR23200_2). Please review.
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: osa
Date: Tue Mar 3 13:38:38 2015 +0300
0023200: Visualization - prevent multiple triangulating of a shape that already has been triangulated
Add new flag IsAutoTriangulated to Prs3d_Drawer. It is True by default.
If this flag is True automatic re-triangulation with deflection-check logic will be applied.
Else this feature will be disable and triangulation is expected to be computed by application itself.
Change the syntax of vdefalts command.
Add new parameter -autoTriang for check of AutoTriangulated functionality.
[revision removed]
Detailed log of new commits:
Author: osa
Date: Tue Mar 3 13:38:38 2015 +0300
0023200: Visualization - prevent multiple triangulating of a shape that already has been triangulated
Add new flag IsAutoTriangulated to Prs3d_Drawer. It is True by default.
If this flag is True automatic re-triangulation with deflection-check logic will be applied.
Else this feature will be disable and triangulation is expected to be computed by application itself.
Change the syntax of vdefalts command.
Add new parameter -autoTriang for check of AutoTriangulated functionality.
This patch was rebased to CR25773_4 and updated.
Now the patch is ready for review (branch CR23200_3).
Now the patch is ready for review (branch CR23200_3).
Please test the patch.
Dear Commenter 1,
Branch CR23200_3 from occt git-repository (and CR25773_4 from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested.
[revision removed]
[revision removed]
Number of compiler warnings:
occt component:
Linux: 18 (18 on master)
Windows: 2 (2 on master)
products component:
Linux: 11 (11 on master)
Windows: 4 (4 on master)
Regressions/Differences:
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/summary.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/summary.html
bugs xde(005) bug23969
Testing cases:
bugs vis(004) bug23200 - OK
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/bugs/vis/bug23200.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/bugs/vis/bug23200.html
bugs vis(004) bug23200_1 - OK
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/bugs/vis/bug23200_1.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/bugs/vis/bug23200_1.html
Testing on Linux:
Total MEMORY difference: 91462893 / 91738013
Total CPU difference: 59634.060000000194 / 59489.119999999995
Testing on Windows:
Total MEMORY difference: 57835644 / 57847876
Total CPU difference: 41304.171875 / 38907.609375
There are differences in images found by testdiff:
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/diff-Debian60-64.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/diff-Windows-64-VC10.html
Branch CR23200_3 from occt git-repository (and CR25773_4 from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested.
[revision removed]
[revision removed]
Number of compiler warnings:
occt component:
Linux: 18 (18 on master)
Windows: 2 (2 on master)
products component:
Linux: 11 (11 on master)
Windows: 4 (4 on master)
Regressions/Differences:
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/summary.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/summary.html
bugs xde(005) bug23969
Testing cases:
bugs vis(004) bug23200 - OK
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/bugs/vis/bug23200.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/bugs/vis/bug23200.html
bugs vis(004) bug23200_1 - OK
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/bugs/vis/bug23200_1.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/bugs/vis/bug23200_1.html
Testing on Linux:
Total MEMORY difference: 91462893 / 91738013
Total CPU difference: 59634.060000000194 / 59489.119999999995
Testing on Windows:
Total MEMORY difference: 57835644 / 57847876
Total CPU difference: 41304.171875 / 38907.609375
There are differences in images found by testdiff:
http://occt-tests/CR23200-3-CR25773-4-occt-64/Debian60-64/diff-Debian60-64.html
http://occt-tests/CR23200-3-CR25773-4-occt-64/Windows-64-VC10/diff-Windows-64-VC10.html
The changes are OK - the faces without triangulation are now displayed in wireframe.
Please switch to TESTED.
Please switch to TESTED.
Sorry, what about test bugs xde bug23969 -- why it is reported as regression?
Branch [archived branch] has been updated by Commenter 3.
[revision removed]
Detailed log of new commits:
Author: Commenter 3
Date: Thu Mar 5 11:12:57 2015 +0300
Adjust camera position in test case bugs/xde/bug23969
[revision removed]
Detailed log of new commits:
Author: Commenter 3
Date: Thu Mar 5 11:12:57 2015 +0300
Adjust camera position in test case bugs/xde/bug23969
> Sorry, what about test bugs xde bug23969 -- why it is reported as regression?
The camera position within test case has been corrected.
The camera position within test case has been corrected.
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Related records
- #0023501 · related to · closedRedundant triangulation cleaning/generation (1) in AIS_Shape.cxx
- #0026014 · parent of · closedVisualization - the IsAutoTriangulated flag is ignored for AIS_ColoredShape
- #0032247 · parent of · closedVIS, IVtkOCC_ShapeMesher - allow disabling auto-triangulation behavior
- #0023966 · related to · closedVoxel_FastConverter performs unnecessary triangulation.
- #0024013 · related to · closedVoxel_FastConverter is able to use existing triangulation
- #0025825 · related to · closedDraw Harness, XSDRAWSTLVRML - drop command tovrml and XSDRAWSTLVRML_ToVRML