At some point I could really use two postprocessing steps which I think are missing.
A) Quadrangulate: same as triangulate only all polygons are broken up into 4 or less edges.
A "Quadrangulate" step might also theoretically try to merge adjacent coplanar triangles into quadrangles, but I think conceptually it would make more sense to run the following step prior to quadrangulation:
B) Merge Adjacent Coplanar Faces: Or whatever you want to call it. It might make sense to go ahead and triangulate the mesh before doing this step. Basically like it sounds, faces on the same plane sharing an edge are combined into the biggest polygon possible.
Also before I go. Does the current build still expect Importers to hand off "Verbose Format" meshes?
And are Importers supposed to set mPrimitiveTypes? Because if I set this in the importer based on what types of primitives the format allows the Validator throws a fit if one of those primitives is not actually in the mesh. So I'm assuming the validation or post processing stuff is supposed to handle this exclusively (because having each importer count the primitive types seems a little ridiculous)
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
>> And I suppose any step that merged coplanar faces would have to do so without tossing out any vertices or else chaos would ensue on the UVs front.
You need to make sure that the result of linear extrapolation of UVs, colors, … across the entire polgon does not change during merigng. This might be a bit tricky, so I'd recommend not to remove vertices even if it is possible.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
>> You need to make sure that the result of linear extrapolation of UVs, colors, … across the entire polygon does not change during merging. This might be a bit tricky, so I'd recommend not to remove vertices even if it is possible.
I was (to be clear) suggesting not removing the vertices. I don't think anyone would actually ever want that, but if you could prove it would not change that might be a safe optimization. If to triangle share an edge it's safe to assume I think merging them into a quadrangle on that edge changes nothing (for a traditional triangle based rasterizer anyway)
BTW: If/when someone does go about implementing this (I'd prefer not to end up doing it myself, but please work out the proposed bits/enums in advance if necessary) an algorithm that weights candidate for removal edges based on the internal angles being 90 degrees would be appreciated (eg. this would insure a square grid of quads would come out in squares versus some houndstooth pattern)
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Nitpicking, if the mesh was optimized to remove redundant vertices that should be a separate postprocess flag because a lot of the time models are intentionally busted up for vertex based shadow effects and what have you.
Are there plans should the number of postprocess flags go over 32bits? There really should not be a "policy" of trying to fit everything into 32 or 64bits / toss out whatever seems less important.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
>> There really should not be a "policy" of trying to fit
Uhm … let's switch them to 64 bit for now. Planning with more than 64 steps if we have only ~30 so far violates YAGNI.
That's a breaking API change, of course. But fine during the current development circle. Patches appreciated (iirc stdint.h is included in the public headers, so uint64_t is available).
And, please, can we discuss that on the mailing list?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I would prefer to use the mailing list more for stuff that should not be aired out in public. I'm really not a fan of lists and since the activity level is not super high I'd prefer it stay that way.
Offtopic: Normalize Normals would also be worth assigning to 64bits (before too late)
@ulfjorensen, I did not realize there was a feature request framework. I cannot tell if your entry on my behalf is in earnest or jest. If Aramis can agree on what to call the enums and reserve some values I can implement this. I don't see how the value of it is not obvious. If you're going to be *actually* working with a model / converting it into a format not designed for bloated triangle representation (possibly without even enough space to fit such models) then it's a must (for convenience sake)
"Polygons have undesirable properties which make them useless for most applications."
Planar polygons are desirable for any modeling application. If you don't allow for floating vertices, and treat all polygons as a fan, you don't have to worry about anything.
"Lowest priority because almost all users request triangulation anyways"
My that's a tiny problem domain you have there.
"and definitely only when bordering vertex attributes match."
Any operations applied to faces should happen at the index level after all the vertex stuff is done (in other words, if the index is equal the attributes are equal)
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
If possible I would like to go ahead and setup a simple Quadrangulate post process that would just break faces down to four edges instead of three. But I have a feeling the process steps might depend on the mesh being triangulated, since I don't really understand how the processing pipeline is setup.
If it is possible I'd like to know if it would be reasonable to generalize some of the code in the triangulate process so the number 4 could just be substituted for 3 in a few places / if that would work well enough.
If there is a quality control thing an enum for hte Quadrangulate process could be kept hidden from aiPostProcess.h until things are worked out.
My vision is only coplanar quads would be honored. If doable non-planar could also be allowed via the configuration file stuff but would other wise be busted up if run in place of triangulate. If run after triangulate a quadrangulate step would not make sense without a coplanar merge step.
The coplanar merge step I think for sake of sanity should have a requirement of two edges per vertex beyond possibly some configuration file stuff.
Anyway I don't really understand the post process progression so please advise (if you have the time)
Btw, in the Triangulate process great length appears to be gone to for non-convex polygons. Is there any documentation about how to interpret aiFaces with more than 3 indices? Ie. are they not simple fans / do existing importers deploy faces with degenerate elements?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
>> If it is possible I'd like to know if it would be reasonable to generalize some of the code in the triangulate process so the number 4
I am not sure if ear cutting is directly applicable to quads. You might run the same algorithm, however, and merge adjacent triangles. Still, I would not reuse code from TriangulateProcess.
>> But I have a feeling the process steps might depend on the mesh being triangulated
ImproveCacheLocality is the only process I know of with such a dependency.
>> f there is a quality control thing an enum for hte Quadrangulate process could be kept hidden from aiPostProcess.h
Not really because one must explicitly specify another pp flag to get the updated behaviour, so existing users are not harmed. Feel free to take the next free enum value, if there is one (I think so).
>> Is there any documentation about how to interpret aiFaces with more than 3 indices?
would more doc be needed? they're polgons. no guarantees are made - they are not necessarily planar, may contain holes, be self-intersecting …
>> do existing importers deploy faces with degenerate elements?
Many models contain degenerate elements, either erroneously produced during modelling or inserted by ancient padding algorithms targeting 10 year old hardware – there is a reason the FindDegenerate step exists.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hm, here my old idea of a dependecy-graph for processing steps can be useful. It is just a directed graph which represents the dependencies for each processing step. So if there is a processing step which cannot be used after that quadrangulate step we can descripe this by such a graph. We just have to remove the not compatible steps of the graph if a quadrangulate is part of the graph.
Unfortunately I stopped my work on that data structure after bereavement in my family. Maybe I should restart the work :o)…
Kimmi
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I don't think quadrangulate is necessarily synonymous with triangulate. Other than triangulate all connectivity steps should come near the end in terms of geometry altering steps and should work on indices period.
As for aiFaces. Just saying "they're polygons" isn't really good enough. Are they fans? Should they be regarded as two-sided? Most complex polygon models I would think would be more involved than a straight list of indices, but honestly I don't actually know the history of this. If degenerates are used liberally it may be possible to construct a non-convex polygon with holes but I think it would be impossible to make much sense of from a modeling pov. I'm assuming most such complex polygons would come from engineering formats. Also I don't think importers of such a format should rely on the post processing steps to account for this but it's understandable if the format is not explicit about the representation of complex polygons.
From the enum pov, I only recommend hiding the value or naming it something like ReservedStepNo2 until it's really ready for use. People might see Quadrangulate and that could appear desirable depending on the application / while not realizing it's not really up to snuff / agreed upon what it should actually be doing. Until there is a coplanar merge step I'd prefer to keep both of them under the radar.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Would it be ok (make sense within the framework) if there was a single post process step called like MakeFacesCoplanar and that step could look for the triangulate/quadrangulate flags and limit its handling of faces in that regard. That would at least avoid the situation where the mesh is rebuilt three times. If neither flag is set then it would merge coplanar (and break non-planar) up to the point all vertices have at least two connecting edges.
I would not have thought this before but if all the steps are so far virtually independent it would be good to keep them that way, even if steps inspect other flags in order to get their job done.
Are existing dependencies just an implementation thing or are they really hard dependencies?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
^I think that is a more reasonable approach perhaps. There would then be three flags working in concert, the triangulate, quadrangulate, and coplanar flags. If the Coplanar flag is not set then quadrangulate just keeps quads without regard for planarity and triangulate is never run. If coplanar is set the old triangulate step is skipped, that is the coplanar algorithm handles triangulation if the triangulate flag is set.
There might be room for a special flag if both triangulate and quadrangulate were set. This framework would be best to not attempt to merge anything or create arbitrary quads from non-planar pairs of triangles. A separate step could be added to greedily merge coplanar prior to this step.
The real argument for this setup is I think it's simple to implement. Is greater than the sum of its parts. And avoids redundantly remeshing things (which could get ugly for monster files / make people mock Assimp)
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
^I think the correct interpretation of both tri/quadrangulate flags being set in such a scenario would be to give priority to quads but to regard the mesh as if it was pre-triangulated. Which might only make sense to a greedy coplanar merge step because it could then treat a polygon as a collection of potentially coplanar triangles versus a single entity.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
There are no guarantees given on polygons at all. The can be planar or non-planar, concave or convex, self-intersecting or anything. The actual properties of polygons depend on the format and on the exporters used to generate the file.
Polygons can be triangulated as triangle fans in most cases, but not in all cases. The Triangulate post processing step is that complex for a simple reason: it was necessary to handle all those polygons.
If you like to get started on the Quadrangulate post process, feel free to do so. Pick a enum value, create the class for the step and register it in the Importer constructor. The order of sequence there is also the order in which post processing steps are executed. If you want a properly indexed mesh to work on, not the verbose representation, place your step after the JoinVerticesStep.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Quick glance looks like all of the enum values are also in order of high order bits. If so can that rule be broken? Is there any attempt to be backwards compatible build to build?
I still think there's merit in treating the flags as a matrix of possible outcomes versus a strict linear progression. Like I said many of the steps are redundant applied linearly and would result in a lot of unnecessary computation. Also the implementation would be more straight forward if there was an ounce of self awareness in the pipeline.
I'm still confused about your description of greater than three vertex faces. From the interface end all outgoing assets are presumably in a unified format. Also the triangulate process must have a unified conception of how the face vertices are to be interpreted or it could not do it's job… or at the least it can only do it one way. Think about it.
Anyway the docs (or the surrounding comments at least) don't say afaik. I have not seen any doc efforts geared toward Assimp from the development end.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I had updated my checkout a few days ago, the Verbose requirement still seems to be there. And I thought I'd mention the Make Verbose process seems to have a depedency on the Triangulate process. It has an assertion anyway which appears to be pure triangle centric.
How many processes BTW are dependent on the mesh being Verbose Format?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
All PPsteps until the JoinUniqueVertices step depend on the verbose representation of the mesh data. And of course: there's only a single approach to triangulation. If there is additional knowledge available on how to triangulate a certion primitive in a single file format, the corresponding loader will already take care of it. But all file formats I know of do not specify the triangulation process. The current triangulation process simply represents the optimal method we found to work with most of the assets.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
At some point I could really use two postprocessing steps which I think are missing.
A) Quadrangulate: same as triangulate only all polygons are broken up into 4 or less edges.
A "Quadrangulate" step might also theoretically try to merge adjacent coplanar triangles into quadrangles, but I think conceptually it would make more sense to run the following step prior to quadrangulation:
B) Merge Adjacent Coplanar Faces: Or whatever you want to call it. It might make sense to go ahead and triangulate the mesh before doing this step. Basically like it sounds, faces on the same plane sharing an edge are combined into the biggest polygon possible.
Also before I go. Does the current build still expect Importers to hand off "Verbose Format" meshes?
And are Importers supposed to set mPrimitiveTypes? Because if I set this in the importer based on what types of primitives the format allows the Validator throws a fit if one of those primitives is not actually in the mesh. So I'm assuming the validation or post processing stuff is supposed to handle this exclusively (because having each importer count the primitive types seems a little ridiculous)
PS: mPrimitiveTypes is in aiMesh.
And I suppose any step that merged coplanar faces would have to do so without tossing out any vertices or else chaos would ensue on the UVs front.
Such a Quadrangulate Step would be fine, I think. Same for MergeAdjacentFaces.
>> Does the current build still expect Importers to hand off "Verbose Format" meshes?
It does - hold on, I'll try to change that this afternoon.
>> because having each importer count the primitive types seems a little ridiculous
Pleas see the docs for BaseImporter.
>> And I suppose any step that merged coplanar faces would have to do so without tossing out any vertices or else chaos would ensue on the UVs front.
You need to make sure that the result of linear extrapolation of UVs, colors, … across the entire polgon does not change during merigng. This might be a bit tricky, so I'd recommend not to remove vertices even if it is possible.
>> You need to make sure that the result of linear extrapolation of UVs, colors, … across the entire polygon does not change during merging. This might be a bit tricky, so I'd recommend not to remove vertices even if it is possible.
I was (to be clear) suggesting not removing the vertices. I don't think anyone would actually ever want that, but if you could prove it would not change that might be a safe optimization. If to triangle share an edge it's safe to assume I think merging them into a quadrangle on that edge changes nothing (for a traditional triangle based rasterizer anyway)
BTW: If/when someone does go about implementing this (I'd prefer not to end up doing it myself, but please work out the proposed bits/enums in advance if necessary) an algorithm that weights candidate for removal edges based on the internal angles being 90 degrees would be appreciated (eg. this would insure a square grid of quads would come out in squares versus some houndstooth pattern)
Nitpicking, if the mesh was optimized to remove redundant vertices that should be a separate postprocess flag because a lot of the time models are intentionally busted up for vertex based shadow effects and what have you.
Are there plans should the number of postprocess flags go over 32bits? There really should not be a "policy" of trying to fit everything into 32 or 64bits / toss out whatever seems less important.
>> There really should not be a "policy" of trying to fit
Uhm … let's switch them to 64 bit for now. Planning with more than 64 steps if we have only ~30 so far violates YAGNI.
That's a breaking API change, of course. But fine during the current development circle. Patches appreciated (iirc stdint.h is included in the public headers, so uint64_t is available).
And, please, can we discuss that on the mailing list?
I opened a feature request for this topic - see here. Just to make sure it doesn't get lost over time.
I would prefer to use the mailing list more for stuff that should not be aired out in public. I'm really not a fan of lists and since the activity level is not super high I'd prefer it stay that way.
Offtopic: Normalize Normals would also be worth assigning to 64bits (before too late)
@ulfjorensen, I did not realize there was a feature request framework. I cannot tell if your entry on my behalf is in earnest or jest. If Aramis can agree on what to call the enums and reserve some values I can implement this. I don't see how the value of it is not obvious. If you're going to be *actually* working with a model / converting it into a format not designed for bloated triangle representation (possibly without even enough space to fit such models) then it's a must (for convenience sake)
"Polygons have undesirable properties which make them useless for most applications."
Planar polygons are desirable for any modeling application. If you don't allow for floating vertices, and treat all polygons as a fan, you don't have to worry about anything.
"Lowest priority because almost all users request triangulation anyways"
My that's a tiny problem domain you have there.
"and definitely only when bordering vertex attributes match."
Any operations applied to faces should happen at the index level after all the vertex stuff is done (in other words, if the index is equal the attributes are equal)
If possible I would like to go ahead and setup a simple Quadrangulate post process that would just break faces down to four edges instead of three. But I have a feeling the process steps might depend on the mesh being triangulated, since I don't really understand how the processing pipeline is setup.
If it is possible I'd like to know if it would be reasonable to generalize some of the code in the triangulate process so the number 4 could just be substituted for 3 in a few places / if that would work well enough.
If there is a quality control thing an enum for hte Quadrangulate process could be kept hidden from aiPostProcess.h until things are worked out.
My vision is only coplanar quads would be honored. If doable non-planar could also be allowed via the configuration file stuff but would other wise be busted up if run in place of triangulate. If run after triangulate a quadrangulate step would not make sense without a coplanar merge step.
The coplanar merge step I think for sake of sanity should have a requirement of two edges per vertex beyond possibly some configuration file stuff.
Anyway I don't really understand the post process progression so please advise (if you have the time)
Btw, in the Triangulate process great length appears to be gone to for non-convex polygons. Is there any documentation about how to interpret aiFaces with more than 3 indices? Ie. are they not simple fans / do existing importers deploy faces with degenerate elements?
>> If it is possible I'd like to know if it would be reasonable to generalize some of the code in the triangulate process so the number 4
I am not sure if ear cutting is directly applicable to quads. You might run the same algorithm, however, and merge adjacent triangles. Still, I would not reuse code from TriangulateProcess.
>> But I have a feeling the process steps might depend on the mesh being triangulated
ImproveCacheLocality is the only process I know of with such a dependency.
>> f there is a quality control thing an enum for hte Quadrangulate process could be kept hidden from aiPostProcess.h
Not really because one must explicitly specify another pp flag to get the updated behaviour, so existing users are not harmed. Feel free to take the next free enum value, if there is one (I think so).
>> Is there any documentation about how to interpret aiFaces with more than 3 indices?
would more doc be needed? they're polgons. no guarantees are made - they are not necessarily planar, may contain holes, be self-intersecting …
>> do existing importers deploy faces with degenerate elements?
Many models contain degenerate elements, either erroneously produced during modelling or inserted by ancient padding algorithms targeting 10 year old hardware – there is a reason the FindDegenerate step exists.
Hm, here my old idea of a dependecy-graph for processing steps can be useful. It is just a directed graph which represents the dependencies for each processing step. So if there is a processing step which cannot be used after that quadrangulate step we can descripe this by such a graph. We just have to remove the not compatible steps of the graph if a quadrangulate is part of the graph.
Unfortunately I stopped my work on that data structure after bereavement in my family. Maybe I should restart the work :o)…
Kimmi
I don't think quadrangulate is necessarily synonymous with triangulate. Other than triangulate all connectivity steps should come near the end in terms of geometry altering steps and should work on indices period.
As for aiFaces. Just saying "they're polygons" isn't really good enough. Are they fans? Should they be regarded as two-sided? Most complex polygon models I would think would be more involved than a straight list of indices, but honestly I don't actually know the history of this. If degenerates are used liberally it may be possible to construct a non-convex polygon with holes but I think it would be impossible to make much sense of from a modeling pov. I'm assuming most such complex polygons would come from engineering formats. Also I don't think importers of such a format should rely on the post processing steps to account for this but it's understandable if the format is not explicit about the representation of complex polygons.
From the enum pov, I only recommend hiding the value or naming it something like ReservedStepNo2 until it's really ready for use. People might see Quadrangulate and that could appear desirable depending on the application / while not realizing it's not really up to snuff / agreed upon what it should actually be doing. Until there is a coplanar merge step I'd prefer to keep both of them under the radar.
Would it be ok (make sense within the framework) if there was a single post process step called like MakeFacesCoplanar and that step could look for the triangulate/quadrangulate flags and limit its handling of faces in that regard. That would at least avoid the situation where the mesh is rebuilt three times. If neither flag is set then it would merge coplanar (and break non-planar) up to the point all vertices have at least two connecting edges.
I would not have thought this before but if all the steps are so far virtually independent it would be good to keep them that way, even if steps inspect other flags in order to get their job done.
Are existing dependencies just an implementation thing or are they really hard dependencies?
^I think that is a more reasonable approach perhaps. There would then be three flags working in concert, the triangulate, quadrangulate, and coplanar flags. If the Coplanar flag is not set then quadrangulate just keeps quads without regard for planarity and triangulate is never run. If coplanar is set the old triangulate step is skipped, that is the coplanar algorithm handles triangulation if the triangulate flag is set.
There might be room for a special flag if both triangulate and quadrangulate were set. This framework would be best to not attempt to merge anything or create arbitrary quads from non-planar pairs of triangles. A separate step could be added to greedily merge coplanar prior to this step.
The real argument for this setup is I think it's simple to implement. Is greater than the sum of its parts. And avoids redundantly remeshing things (which could get ugly for monster files / make people mock Assimp)
^I think the correct interpretation of both tri/quadrangulate flags being set in such a scenario would be to give priority to quads but to regard the mesh as if it was pre-triangulated. Which might only make sense to a greedy coplanar merge step because it could then treat a polygon as a collection of potentially coplanar triangles versus a single entity.
There are no guarantees given on polygons at all. The can be planar or non-planar, concave or convex, self-intersecting or anything. The actual properties of polygons depend on the format and on the exporters used to generate the file.
Polygons can be triangulated as triangle fans in most cases, but not in all cases. The Triangulate post processing step is that complex for a simple reason: it was necessary to handle all those polygons.
If you like to get started on the Quadrangulate post process, feel free to do so. Pick a enum value, create the class for the step and register it in the Importer constructor. The order of sequence there is also the order in which post processing steps are executed. If you want a properly indexed mesh to work on, not the verbose representation, place your step after the JoinVerticesStep.
Quick glance looks like all of the enum values are also in order of high order bits. If so can that rule be broken? Is there any attempt to be backwards compatible build to build?
I still think there's merit in treating the flags as a matrix of possible outcomes versus a strict linear progression. Like I said many of the steps are redundant applied linearly and would result in a lot of unnecessary computation. Also the implementation would be more straight forward if there was an ounce of self awareness in the pipeline.
I'm still confused about your description of greater than three vertex faces. From the interface end all outgoing assets are presumably in a unified format. Also the triangulate process must have a unified conception of how the face vertices are to be interpreted or it could not do it's job… or at the least it can only do it one way. Think about it.
Anyway the docs (or the surrounding comments at least) don't say afaik. I have not seen any doc efforts geared toward Assimp from the development end.
I had updated my checkout a few days ago, the Verbose requirement still seems to be there. And I thought I'd mention the Make Verbose process seems to have a depedency on the Triangulate process. It has an assertion anyway which appears to be pure triangle centric.
How many processes BTW are dependent on the mesh being Verbose Format?
All PPsteps until the JoinUniqueVertices step depend on the verbose representation of the mesh data. And of course: there's only a single approach to triangulation. If there is additional knowledge available on how to triangulate a certion primitive in a single file format, the corresponding loader will already take care of it. But all file formats I know of do not specify the triangulation process. The current triangulation process simply represents the optimal method we found to work with most of the assets.