Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 10 of 18

Thread: Primitive restart extended functionality

Hybrid View

  1. #1
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    145

    Primitive restart extended functionality

    Let's start from the problem: it is common to have a mesh built with different types of primitives, but gl*Draw* functions let you draw only one type of primitives per call. So you are either forced to convert all the geometry to one type of primitive (in most cases, GL_TRIANGLE_STRIP is the most optimal solution) or call gl*Draw* multiple times sorting the primitives by their type. Well, primitive restarting indices helped to separate primitives "on the fly" without bothering to call gl*Draw* for each individual primitive or inserting multiple index clones, but still the optimization on the mesh have to be done to combine individual triangles into primitives of the same type. Howether, merging triangles of abstractly-shaped geometry all into strips only, with blind machine algorithms (even advanced ones), results in a considerable quantity of short strips. Some of that "garbage" may even better fit into GL_TRIANGLE_FAN rather than GL_TRIANGLE_STRIP, or even rendered as individual triangles. But as we forced to use strips for all primitives, we still have to use separation indices for each of those small chunks.

    So here is my solution for that mess: let's extend the functionality of the primitive restart index(es) to let it(them) change the primitive mode. In order to do that we need more than one value of index to have a special meaning rather then referencing the corresponding set of vertex attribute. I think, the most elegant way is to state that once the extended functionality of Primitive Restart Index (shortly, PRI) is enabled, then any index, which value is equal or higher than the value specified by glPrimitiveRestartIndex will have the special meaning. If the index is equal to the specified PRI, then the primitive type stays the same (just restarted); if the index is higher than PRI, then the type of the primitive changes, so all subsequent indices will be used to construct the primitive of the new type.

    So what are the rules of converting the special index value into the desired primitive type? Let's have a look on the defined values of all currently known primitives (let's keep legacy types in that table just for consistency purposes):
    GL_POINTS 0x00
    GL_LINES 0x01
    GL_LINE_LOOP 0x02
    GL_LINE_STRIP 0x03
    GL_TRIANGLES 0x04
    GL_TRIANGLE_STRIP 0x05
    GL_TRIANGLE_FAN 0x06
    GL_QUADS 0x07
    GL_QUAD_STRIP 0x08
    GL_POLYGON 0x09
    GL_LINES_ADJACENCY 0x0A
    GL_LINE_STRIP_ADJACENCY 0x0B
    GL_TRIANGLES_ADJACENCY 0x0C
    GL_TRIANGLE_STRIP_ADJACENCY 0x0D
    GL_PATCHES 0x0E
    So far there are 15 values only, defined as consecutive numbers. The straightforward approach is to think of the index just above the PRI value as a base offset for those numbers. So once the index encountered which is equal to PRI, the primitive will be just restarted, but it's type left unchanged; if the index value is equal to (PRI+1), then the primitive type will switch to GL_POINTS; if index is (PRI+2), then the new primitive type will became a GL_LINES and so on.

    The way I described this may be raw and messy, I know, but I hope the idea will find the support.
    The extended primitive restart functionality will let the meshes to be constructed with primitives of different types and greatly simplify their drawing and storing in files. The quntity of gl*DrawElements* calls required to draw a single mesh will be reduced to 1 single call as all required information may be stored right in the GL_ELEMENT_ARRAY_BUFFER making the "mode" parameter of a set of gl*DrawElements* functions obsolete.
    Last edited by Yandersen; 06-12-2014 at 04:08 PM.

  2. #2
    Senior Member OpenGL Pro
    Join Date
    Jan 2007
    Posts
    1,294
    Actually strips have not been the most optimal primitive type for a long time. glDrawElements with GL_TRIANGLES is preferred (you can arrange the data in strip order if you wish, but you don't have to). id software pushed this as the optimal path for Quake III (in 1999), they give better vertex reuse, and this has been what vendors optimize around. See also http://tomsdxfaq.blogspot.ie/2005_12_01_archive.html

    Let me say this just once, because academics are still spending time and money researching this subject. You're wasting your time. Strips are obsolete - they are optimising for hardware that no longer exists. Indexed vertex caches are much better at this than non-indexed strips, and the hardware is totally ubiquitous. Please go and spend your time and money researching something more interesting.
    The exception is if you're talking about a mobile device where you know that strips are still preferred, but that's OpenGL ES, not OpenGL

  3. #3
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    145
    "...Indexed vertex caches are much better at this than non-indexed strips..." - what I see here is a comparison between indexed way of drawing of the most unoptimal primitives (GL_TRIANGLES) vs indexed GL_TRIANGLE_STRIPS - this emphasizes the performance gain from vertex post-processing cache, it has nothing to do with the actual type of the primitive. If the comparison will be made between indexed drawing of both of those types, no doubt strips will win. Well, at least the size of the index buffer will be smaller.

    Drawing 2 connected triangles independently will require 6 invocations of a vertex shader, but if they are drawn using GL_TRIANGLE_FAN or GL_TRIANGLE_STRIPS, there will be only 4 invocations. Well, with the help of vertex post-processing cache the number of vertex shader invocations may be equal to the number of processed vertices, yes, but still there is a gain achieved by the reduction of the index buffer size, as triangles take 3*n indices and strips (or fans) take 2+n+1 indices (including the PRI), so if there is 2 or more connected triangles in a mesh, it is better to use strips or fan primitive to draw them. And in most cases any triangle in a mesh has at least 3 neighbors.

  4. #4
    Junior Member Regular Contributor
    Join Date
    Dec 2009
    Posts
    247
    Quote Originally Posted by Yandersen View Post
    Drawing 2 connected triangles independently will require 6 invocations of a vertex shader, but if they are drawn using GL_TRIANGLE_FAN or GL_TRIANGLE_STRIPS, there will be only 4 invocations. Well, with the help of vertex post-processing cache the number of vertex shader invocations may be equal to the number of processed vertices, yes, but still there is a gain achieved by the reduction of the index buffer size, as triangles take 3*n indices and strips (or fans) take 2+n+1 indices (including the PRI), so if there is 2 or more connected triangles in a mesh, it is better to use strips or fan primitive to draw them. And in most cases any triangle in a mesh has at least 3 neighbors.
    For a vertex cache of size 2 or more there will be only 4 invocations for indexed triangles either.

    The gain in index buffer size is only relevant if you actually build long strips, but in that case you can't make effective use of the vertex cache:

    In an optimal triangle mesh, every vertex is part of 6 triangles, but in a strip it is only part of at most 3 triangles, so (on average) every vertex has to be part of two strips. If you optimize for long strips to reduce memory consumption, you'll no longer have that vertex cached the second time it is needed, so you need twice the number of vertex shader invocations for strips.

  5. #5
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    145
    So am I just outdated? Are you guys saying everybody nowadays using triangles only and nobody bother with strips and fans? So there will be no use for the proposed extension at all?

    Quote Originally Posted by mbentrup View Post
    In an optimal triangle mesh, every vertex is part of 6 triangles, but in a strip it is only part of at most 3 triangles, so (on average) every vertex has to be part of two strips. If you optimize for long strips to reduce memory consumption, you'll no longer have that vertex cached the second time it is needed, so you need twice the number of vertex shader invocations for strips.
    If I have such mesh that could be tessellated onto long strips - long enough to extend the capacity of the cach - I can't imagine how could I draw it with triangles to make a better use of cache. Drawing it area-by-area will still make border vertices outcached. Perhaps it may be even worse than with strips. Still, strips can be trimmed into the smaller sizes, and even after that the amount of indices will be smaller comparing to what the individual triangles will take.
    Last edited by Yandersen; 06-13-2014 at 03:13 PM.

  6. #6
    Senior Member OpenGL Pro
    Join Date
    Jan 2007
    Posts
    1,294
    Quote Originally Posted by mbentrup View Post
    In an optimal triangle mesh, every vertex is part of 6 triangles, but in a strip it is only part of at most 3 triangles, so (on average) every vertex has to be part of two strips. If you optimize for long strips to reduce memory consumption, you'll no longer have that vertex cached the second time it is needed, so you need twice the number of vertex shader invocations for strips.
    And vertices are much bigger than indices too, so the saving on vertices more than offsets the increased index count.

    Quote Originally Posted by Yandersen View Post
    So am I just outdated? Are you guys saying everybody nowadays using triangles only and nobody bother with strips and fans? So there will be no use for the proposed extension at all?
    Strips are still relevant in the mobile world and this would probably be useful for GL ES. There may be some cost from both restarting a primitive and switching the primitive type, but the saving from fewer draw calls may offset that (draw calls are a much bigger deal with ES than they are on the desktop).
    Last edited by mhagain; 06-13-2014 at 04:51 PM.

  7. #7
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    145
    Let's skip on arguing what type of the primitive is *the best* and focus on the actual idea of the proposed extension. The most important question, as I see that, is the performance. Is it possible to predict if switching the primitive type along with primitive restarting will considerably slow down the performance comparing to the simple primitive restarting? Is there a way to implement the proposed primitive switching functionality and keep rendering speed the same?

    Maybe the way of primitive switching I described earlier is not the best one for implementation. Maybe the switching indices has to be set independently using some special function:

    Code :
    //glPrimitiveSwitchingIndexMode(GLenum index, GLenum mode)
    glEnable(GL_PRIMITIVE_RESTART);
    glPrimitiveRestartIndex(252);
    glPrimitiveSwitchingIndexMode(GL_PRIMITIVE_SWITCHING_INDEX0, GL_TRIANGLE_FAN); //The actual index value is 253
    glPrimitiveSwitchingIndexMode(GL_PRIMITIVE_SWITCHING_INDEX1, GL_TRIANGLES); //The actual index value is 254
    glEnable(GL_PRIMITIVE_SWITCHING_INDEX0); //Now the index 253 will switch the primitive type to GL_TRIANGLE_FAN
    glEnable(GL_PRIMITIVE_SWITCHING_INDEX1); //Now the index 254 will switch the primitive type to GL_TRIANGLES

    In other words, the implementation will have a set of supported primitive switching indices (PSI) ranging from GL_PRIMITIVE_SWITCHING_INDEX0 to GL_PRIMITIVE_SWITCHING_INDEXi, where i is equal to GL_MAX_PRIMITIVE_SWITCHING_INDICES-1. Each of those index binding points have an index value implicitly associated with them. That value is based on the primitive restart index, so for the target GL_PRIMITIVE_SWITCHING_INDEX0 the actual index value will be equal to PRI+1; for GL_PRIMITIVE_SWITCHING_INDEX1 it is PRI+2 and so on. The actual number of supported PSI is implementation dependent and may be smaller than the number of supported primitive types. Maybe. I don't know, I am not a developer.
    So we associate the primitive types for different PSI, then enable that PSI.

    It is just an another way to implement the index-based primitive switching.
    It can also be extended. F.e. if some index value is set to mode GL_NONE, let such index to be the so called termination index, acting just like 0 in character strings, resulting in abortion of index array execution:
    Code :
    glPrimitiveSwitchingIndexMode(GL_PRIMITIVE_SWITCHING_INDEX2, GL_NONE); //Once the index equal to PRI+3 encountered, all subsequent indices will be ignored
    glEnable(GL_PRIMITIVE_SWITCHING_INDEX2); //Now the index 255 will stop the index array execution
    Last edited by Yandersen; 06-13-2014 at 09:21 PM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •