home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / System / Mesa-3.1 / src / vbcull.c < prev    next >
C/C++ Source or Header  |  2000-01-07  |  23KB  |  981 lines
  1. /* $Id: vbcull.c,v 1.7 1999/11/08 15:28:58 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  3.1
  6.  * 
  7.  * Copyright (C) 1999  Brian Paul   All Rights Reserved.
  8.  * 
  9.  * Permission is hereby granted, free of charge, to any person obtaining a
  10.  * copy of this software and associated documentation files (the "Software"),
  11.  * to deal in the Software without restriction, including without limitation
  12.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13.  * and/or sell copies of the Software, and to permit persons to whom the
  14.  * Software is furnished to do so, subject to the following conditions:
  15.  * 
  16.  * The above copyright notice and this permission notice shall be included
  17.  * in all copies or substantial portions of the Software.
  18.  * 
  19.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20.  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22.  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23.  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24.  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25.  */
  26.  
  27. /*
  28.  * New (3.1) transformation code written by Keith Whitwell.
  29.  */
  30.  
  31.  
  32. #ifdef PC_HEADER
  33. #include "all.h"
  34. #else
  35. #ifndef XFree86Server
  36. #include <stdio.h>
  37. #else
  38. #include "GL/xf86glx.h"
  39. #endif
  40. #include "context.h"
  41. #include "macros.h"
  42. #include "types.h"
  43. #include "vb.h"
  44. #include "vbcull.h"
  45. #include "vbrender.h"
  46. #include "xform.h"
  47. #endif
  48.  
  49.  
  50. /* Culling for vertices and primitives.
  51.  * (C) Keith Whitwell, December 1998.
  52.  *
  53.  * These functions build bitmasks which can be used to shortcircuit
  54.  * lighting, fogging and texture calculations, and to convert
  55.  * two-sided lighting into one-sided on a per-vertex basis.
  56.  *
  57.  * Each of these functions returns a value 'cullcount'.  The meaning
  58.  * of this value just has to satisfy the requirements:
  59.  *
  60.  *    cullcount == VB->Count implies the entire vb has been culled and
  61.  *    can be discarded.
  62.  * 
  63.  *    cullcount == 0 implies that every vertex in the buffer is required
  64.  *    and that the cullmask can be ignored for transformation 
  65.  *    and lighting.
  66.  * 
  67.  */
  68.  
  69.  
  70. const char *gl_prim_name[GL_POLYGON+2] = {
  71.    "GL_POINTS",
  72.    "GL_LINES",
  73.    "GL_LINE_LOOP",
  74.    "GL_LINE_STRIP",
  75.    "GL_TRIANGLES",
  76.    "GL_TRIANGLE_STRIP",
  77.    "GL_TRIANGLE_FAN",
  78.    "GL_QUADS",
  79.    "GL_QUAD_STRIP",
  80.    "GL_POLYGON",
  81.    "culled primitive"
  82. };
  83.  
  84. static GLuint gl_cull_points( struct vertex_buffer *VB,
  85.                   GLuint start, 
  86.                   GLuint count,
  87.                   GLuint parity,
  88.                   CONST GLfloat (*proj)[4])
  89. {
  90.    const GLubyte *clipmask = VB->ClipMask;
  91.    GLubyte *cullmask = VB->CullMask;
  92.    GLuint i, cullcount = 0;
  93.  
  94.    (void) parity;
  95.    (void) proj;
  96.  
  97.    /* This is pretty pointless.  (arf arf)
  98.     */
  99.    for (i=start+1;i<count;i++) {
  100.       if (clipmask[i] == 0) 
  101.      cullmask[i] = VERT_FACE_FRONT | PRIM_FACE_FRONT;
  102.       else {
  103.      cullcount++;
  104.       }
  105.    }
  106.    return cullcount;
  107. }
  108.  
  109.  
  110. /* Covers all the non-polygonal primitives when only area culling is
  111.  * activated.
  112.  */
  113. static GLuint gl_cull_points_neither( struct vertex_buffer *VB,
  114.                       GLuint start, 
  115.                       GLuint count,
  116.                       GLuint parity,
  117.                       CONST GLfloat (*proj)[4])
  118. {
  119.    GLubyte unculled_prim = VERT_FACE_FRONT|PRIM_FACE_FRONT;
  120.    (void) parity;
  121.    (void) proj;
  122.    MEMSET(VB->CullMask+start, unculled_prim, (count-start)*sizeof(GLubyte));
  123.    return 0;
  124. }
  125.  
  126.  
  127.  
  128. #define CULL_LINE( i1, i, nr )                         \
  129. do {                                     \
  130.    GLubyte ClipOr = VB->ClipMask[i1] | VB->ClipMask[i];             \
  131.                                      \
  132.    if (ClipOr) {                             \
  133.       if (VB->ClipMask[i1] & VB->ClipMask[i] & CLIP_ALL_BITS) {         \
  134.      cullcount+=nr;                             \
  135.       }                                     \
  136.       else {                                 \
  137.      cullmask[i1] |= VERT_FACE_FRONT;                 \
  138.      cullmask[i] |= VERT_FACE_FRONT | PRIM_FACE_FRONT | PRIM_CLIPPED; \
  139.       }                                     \
  140.    } else {                                 \
  141.       cullmask[i1] |= VERT_FACE_FRONT;                     \
  142.       cullmask[i] |= VERT_FACE_FRONT | PRIM_FACE_FRONT;             \
  143.    }                                     \
  144. } while (0)
  145.  
  146.  
  147.  
  148. static GLuint gl_cull_lines( struct vertex_buffer *VB,
  149.                  GLuint start, 
  150.                  GLuint count, 
  151.                  GLuint parity, 
  152.                  CONST GLfloat (*proj)[4])
  153. {
  154.    GLubyte *cullmask = VB->CullMask;
  155.    GLuint cullcount = 0;
  156.    GLuint i;
  157.    GLuint last = count - 1;
  158.  
  159.    (void) parity;
  160.    (void) proj;
  161.  
  162.    for (i = start; i < last ; i += 2) {
  163.       CULL_LINE(i, i+1, 2);
  164.    }
  165.  
  166.    if (i != last)
  167.       cullcount++;
  168.  
  169.    return cullcount;
  170. }
  171.  
  172.  
  173. static GLuint gl_cull_line_strip( struct vertex_buffer *VB,
  174.                   GLuint start, 
  175.                   GLuint count, 
  176.                   GLuint parity, 
  177.                   CONST GLfloat (*proj)[4])
  178. {
  179.    GLubyte *cullmask = VB->CullMask;
  180.    GLuint cullcount = 0;
  181.    GLuint i;
  182.    GLuint last = count - 1;
  183.    GLuint nr = 2;
  184.  
  185.    (void) parity;
  186.    (void) proj;
  187.    
  188.    for (i = start; i < last ; i++, nr = 1) {
  189.       CULL_LINE(i, i+1, nr);
  190.    }
  191.  
  192.    if (i != last)
  193.       cullcount++;
  194.  
  195.    return cullcount;
  196. }
  197.  
  198.  
  199. static GLuint gl_cull_line_loop( struct vertex_buffer *VB,
  200.                  GLuint start, 
  201.                  GLuint count, 
  202.                  GLuint parity, 
  203.                  CONST GLfloat (*proj)[4])
  204. {
  205.    GLuint cullcount = 0;
  206.    GLubyte *cullmask = VB->CullMask;
  207.    GLuint i, last = count - 1;
  208.    (void) parity;
  209.    (void) proj;
  210.    if (count - start < 2) 
  211.       return count - start;
  212.  
  213.    for (i = start; i < last ; i++) {
  214.       CULL_LINE(i, i+1, 1);
  215.    }
  216.  
  217.    CULL_LINE(last, start, 1);
  218.  
  219.    return cullcount;
  220. }
  221.  
  222.  
  223. #define CULL_TRI( do_clip, do_area, i2, i1, i0, parity, nr )        \
  224. do {                                    \
  225.    GLubyte ClipOr = 0;                            \
  226.    if (do_clip) {                            \
  227.       ClipOr = (VB->ClipMask[i2] |                    \
  228.         VB->ClipMask[i1] |                    \
  229.         VB->ClipMask[i0]);                    \
  230.    }                                    \
  231.                                     \
  232.    if (do_clip && (ClipOr&CLIP_ALL_BITS))                \
  233.    {                                    \
  234.       if (VB->ClipMask[i2] & VB->ClipMask[i1] & VB->ClipMask[i0] &    \
  235.       CLIP_ALL_BITS)                        \
  236.       {                                    \
  237.      cullcount+=nr;                            \
  238.       }                                    \
  239.       else                                \
  240.       {                                    \
  241.      cullmask[i0]   = cull_faces | PRIM_CLIPPED;            \
  242.      cullmask[i1] |= cull_faces;                    \
  243.      cullmask[i2] |= cull_faces;                    \
  244.       }                                    \
  245.    }                                    \
  246.    else                                    \
  247.    {                                    \
  248.       GLfloat area;                            \
  249.       GLubyte face_flags;                        \
  250.                                     \
  251.       if (do_area) {                            \
  252.      area = ((proj[i2][0] - proj[i0][0]) *                \
  253.          (proj[i1][1] - proj[i0][1]) -                \
  254.          (proj[i2][1] - proj[i0][1]) *                \
  255.          (proj[i1][0] - proj[i0][0]));                \
  256.                                     \
  257.      face_flags = (((area<0.0F) ^ parity) + 1) & cull_faces;    \
  258.       } else {                                \
  259.      face_flags = cull_faces;                    \
  260.       }                                    \
  261.                                     \
  262.       if (!do_area || face_flags)                    \
  263.       {                                    \
  264.      cullmask[i0]  = face_flags | (face_flags << PRIM_FLAG_SHIFT);    \
  265.      cullmask[i1] |= face_flags;                    \
  266.      cullmask[i2] |= face_flags;                    \
  267.      if (do_clip && ClipOr) cullmask[i0] |= PRIM_CLIPPED;        \
  268.       }                                    \
  269.       else                                \
  270.       {                                    \
  271.      cullcount+=nr;                            \
  272.       }                                    \
  273.    }                                    \
  274. } while (0)
  275.  
  276.  
  277.  
  278.  
  279.  
  280. #define CULL_QUAD( do_clip, do_area, i3, i2, i1, i, nr )        \
  281. do {                                    \
  282.    GLubyte ClipOr = 0;                            \
  283.                                     \
  284.    if (do_clip) {                            \
  285.       ClipOr = (VB->ClipMask[i3] |                    \
  286.         VB->ClipMask[i2] |                     \
  287.         VB->ClipMask[i1] |                     \
  288.         VB->ClipMask[i]);                    \
  289.    }                                    \
  290.                                     \
  291.    if (do_clip && (ClipOr&CLIP_ALL_BITS))                \
  292.    {                                    \
  293.       if (VB->ClipMask[i3] & VB->ClipMask[i2] &             \
  294.       VB->ClipMask[i1] & VB->ClipMask[i] &                \
  295.       CLIP_ALL_BITS)                         \
  296.       {                                    \
  297.      cullcount+=nr;                            \
  298.       }                                    \
  299.       else                                \
  300.       {                                    \
  301.      cullmask[i] = cull_faces | PRIM_CLIPPED;            \
  302.      cullmask[i1] = cull_faces | PRIM_CLIPPED;             \
  303.      cullmask[i2] |= cull_faces;             \
  304.      cullmask[i3] |= cull_faces;                     \
  305.       }                                    \
  306.    }                                    \
  307.    else                                 \
  308.    {                                    \
  309.       GLfloat area;                            \
  310.       GLubyte face_flags;                        \
  311.                                           \
  312.       if (do_area) {                            \
  313.      area = ((proj[i1][0] - proj[i3][0]) * /* ex */            \
  314.          (proj[i ][1] - proj[i2][1]) - /* fy */            \
  315.          (proj[i1][1] - proj[i3][1]) * /* ey */            \
  316.          (proj[i ][0] - proj[i2][0])); /* fx */            \
  317.                                         \
  318.      face_flags = (((area<0.0F) ^ face_bit) + 1) & cull_faces;    \
  319.       } else {                                \
  320.      face_flags = cull_faces;                    \
  321.       }                                    \
  322.                                        \
  323.       if (do_area && !face_flags)                    \
  324.       {                                    \
  325.      cullcount+=nr;                            \
  326.       }                                    \
  327.       else                                 \
  328.       {                                    \
  329.      cullmask[i]  = face_flags | (face_flags<<PRIM_FLAG_SHIFT);    \
  330.      cullmask[i1] = face_flags | (face_flags<<PRIM_FLAG_SHIFT);    \
  331.      cullmask[i2] |= face_flags;                    \
  332.      cullmask[i3] |= face_flags;                    \
  333.      if (ClipOr)                            \
  334.         cullmask[i] |= PRIM_CLIPPED;                \
  335.       }                                 \
  336.    }                                    \
  337. } while(0)
  338.  
  339.  
  340. #define DO_AREA 1
  341. #define DO_CLIP 1
  342. #define TAG(x) x
  343. #include "cull_tmp.h"
  344.  
  345.  
  346. #define DO_AREA 1
  347. #define DO_CLIP 0
  348. #define TAG(x) x##_area
  349. #include "cull_tmp.h"
  350.  
  351. #define DO_AREA 0
  352. #define DO_CLIP 1
  353. #define TAG(x) x##_clip
  354. #include "cull_tmp.h"
  355.  
  356.  
  357.  
  358. static GLuint gl_cull_dummy_prim( struct vertex_buffer *VB,
  359.                   GLuint start, 
  360.                   GLuint count, 
  361.                   GLuint parity, 
  362.                   CONST GLfloat (*proj)[4])
  363. {
  364.    (void) VB;
  365.    (void) parity;
  366.    (void) proj;
  367.    return count - start;
  368. }
  369.  
  370.  
  371. /* KW:  Force the vertices which are used in both this and the
  372.  * next vertex buffer to be fully transformed on their first 
  373.  * appearance.  Need to do this because otherwise I would have
  374.  * to try to copy the un-transformed (Obj, Normal) data.  This
  375.  * is difficult in the case of shared normals, and seems
  376.  * to be quite complex in the immediate mode case.  For now,
  377.  * just force the copied vertices to be transformed.
  378.  *
  379.  * KW: Copy now organized to grow towards zero.
  380.  */
  381. static GLuint gl_copy_last_cull( struct vertex_buffer *VB, 
  382.                  GLuint start, GLuint count,
  383.                  GLuint ovf, CONST GLfloat (*proj)[4])
  384. {
  385.    const GLcontext *ctx = VB->ctx;
  386.    GLubyte *cullmask = VB->CullMask;
  387.    GLuint rv = 0;
  388.    (void) start;
  389.    (void) ovf;
  390.    if (cullmask[count-1] == 0) {
  391.       rv++;
  392.       cullmask[count-1] = ctx->Polygon.CullBits;
  393.    }
  394.    VB->CopyCount = 1;
  395.    VB->Copy[2] = count-1;
  396.    COPY_4FV(VB->CopyProj[2], proj[count-1]);
  397.    return rv;
  398. }
  399.  
  400. static GLuint gl_copy_first_and_last_cull( struct vertex_buffer *VB, 
  401.                        GLuint start, 
  402.                        GLuint count, GLuint ovf,
  403.                        CONST GLfloat (*proj)[4] )
  404. {
  405.    const GLcontext *ctx = VB->ctx;
  406.    GLuint rv = 0;
  407.    GLubyte *cullmask = VB->CullMask;
  408.    (void) ovf;
  409.    if (cullmask[count-1] == 0) {
  410.       rv++;
  411.       cullmask[count-1] = ctx->Polygon.CullBits;
  412.    }
  413.    if (cullmask[start] == 0) {
  414.       rv++;
  415.       cullmask[start] = ctx->Polygon.CullBits;
  416.    }
  417.    VB->CopyCount = 2;
  418.    VB->Copy[1] = start;
  419.    VB->Copy[2] = count-1;
  420.    COPY_4FV(VB->CopyProj[1], proj[start]);
  421.    COPY_4FV(VB->CopyProj[2], proj[count-1]);
  422.    return rv;
  423. }
  424.  
  425. /* Must be able to cope with zero or one overflow
  426.  * 
  427.  */
  428. static GLuint gl_copy_last_two_cull( struct vertex_buffer *VB,
  429.                      GLuint start, 
  430.                      GLuint count, GLuint ovf,
  431.                      CONST GLfloat (*proj)[4] )
  432. {
  433.    const GLcontext *ctx = VB->ctx;
  434.    GLubyte *cullmask = VB->CullMask;
  435.    GLuint rv = 0;
  436.    (void) start;
  437.    if (cullmask[count-1] == 0) {
  438.       rv++;
  439.       cullmask[count-1] = ctx->Polygon.CullBits;
  440.    }
  441.    if (cullmask[count-2] == 0) {
  442.       rv++;
  443.       cullmask[count-2] = ctx->Polygon.CullBits;
  444.    }
  445.    
  446.    VB->CopyCount = 2;
  447.    VB->Copy[1] = count-2;
  448.    VB->Copy[2] = count-1;
  449.    COPY_4FV(VB->CopyProj[1], proj[count-2]);
  450.    COPY_4FV(VB->CopyProj[2], proj[count-1]);
  451.  
  452.    if (ovf == 1) {
  453.       if (cullmask[count-3] == 0) {
  454.      rv++;
  455.      cullmask[count-3] = ctx->Polygon.CullBits;
  456.       }
  457.       VB->CopyCount = 3;
  458.       VB->Copy[0] = count-3;
  459.       COPY_4FV(VB->CopyProj[0], proj[count-3]);
  460.    }
  461.  
  462.    return rv;
  463. }
  464.  
  465.  
  466. /* Eg, quads - just copy the overflow, guarenteed to all be culled.
  467.  */
  468. static GLuint gl_copy_overflow_cull( struct vertex_buffer *VB, 
  469.                      GLuint start, GLuint count,
  470.                      GLuint ovf, CONST GLfloat (*proj)[4] )
  471. {
  472.    const GLcontext *ctx = VB->ctx;
  473.    GLubyte *cullmask = VB->CullMask;
  474.    GLuint src_offset = count - ovf;
  475.    GLuint dst_offset = 3 - ovf;
  476.    GLuint i;
  477.    (void) start;
  478.    VB->CopyCount = ovf;
  479.    for (i = 0 ; i < ovf ; i++) {
  480.       cullmask[i+src_offset] = ctx->Polygon.CullBits;
  481.       VB->Copy[i+dst_offset] = i+src_offset;
  482.       COPY_4FV(VB->CopyProj[i+dst_offset], proj[i+src_offset]);
  483.    }
  484.    return ovf;
  485. }
  486.  
  487.  
  488. static GLuint gl_copy_last( struct vertex_buffer *VB,
  489.                 GLuint start, GLuint count,
  490.                 GLuint ovf, CONST GLfloat (*proj)[4])
  491. {
  492.    (void) start;
  493.    (void) ovf;
  494.    VB->CopyCount = 1;
  495.    VB->Copy[2] = count-1;
  496.    COPY_4FV(VB->CopyProj[2], proj[count-1]);
  497.    return 0;
  498. }
  499.  
  500. static GLuint gl_copy_first_and_last( struct vertex_buffer *VB, 
  501.                       GLuint start, 
  502.                       GLuint count,
  503.                       GLuint ovf, CONST GLfloat (*proj)[4])
  504. {
  505.    (void) ovf;
  506.    VB->CopyCount = 2;
  507.    VB->Copy[1] = start;
  508.    VB->Copy[2] = count-1;
  509.    COPY_4FV(VB->CopyProj[1], proj[start]);
  510.    COPY_4FV(VB->CopyProj[2], proj[count-1]);
  511.    return 0;
  512. }
  513.  
  514. static GLuint gl_copy_last_two( struct vertex_buffer *VB, 
  515.                 GLuint start, GLuint count, 
  516.                 GLuint ovf, CONST GLfloat (*proj)[4])
  517. {
  518.    (void) start;
  519.    VB->CopyCount = 2;
  520.    VB->Copy[1] = count-2;
  521.    VB->Copy[2] = count-1;
  522.    COPY_4FV(VB->CopyProj[1], proj[count-2]);
  523.    COPY_4FV(VB->CopyProj[2], proj[count-1]);
  524.  
  525.    if (ovf == 1) {
  526.       VB->CopyCount = 3;
  527.       VB->Copy[0] = count-3;
  528.       COPY_4FV(VB->CopyProj[0], proj[count-3]);
  529.    }
  530.  
  531.    return 0;
  532. }
  533.  
  534. static GLuint gl_copy_overflow( struct vertex_buffer *VB, 
  535.                 GLuint start, 
  536.                 GLuint count,
  537.                 GLuint ovf,
  538.                 CONST GLfloat (*proj)[4] )
  539. {
  540.    GLuint src_offset = count - ovf;
  541.    GLuint dst_offset = 3 - ovf;
  542.    GLuint i;
  543.    (void) start;
  544.    VB->CopyCount = ovf;
  545.    for (i = 0 ; i < ovf ; i++) {
  546.       VB->Copy[i+dst_offset] = i+src_offset;
  547.       COPY_4FV(VB->CopyProj[i+dst_offset], proj[i+src_offset]);
  548.    }
  549.  
  550.    return 0;
  551. }
  552.  
  553.  
  554.  
  555.  
  556.  
  557.  
  558. static void gl_fast_copy_noop( struct vertex_buffer *VB,
  559.                    GLuint start, GLuint count,
  560.                    GLuint ovf)
  561. {
  562.    (void) start;
  563.    (void) ovf;
  564.    (void) VB;
  565.    (void) count;
  566. }
  567.  
  568. static void gl_fast_copy_last( struct vertex_buffer *VB,
  569.                    GLuint start, GLuint count,
  570.                    GLuint ovf)
  571. {
  572.    (void) start;
  573.    (void) ovf;
  574.    VB->CopyCount = 1;
  575.    VB->Copy[2] = count-1;
  576. }
  577.  
  578. static void gl_fast_copy_first_and_last( struct vertex_buffer *VB, 
  579.                      GLuint start, 
  580.                      GLuint count,
  581.                      GLuint ovf)
  582. {
  583.    (void) ovf;
  584.    VB->CopyCount = 2;
  585.    VB->Copy[1] = start;
  586.    VB->Copy[2] = count-1;
  587. }
  588.  
  589. static void gl_fast_copy_last_two( struct vertex_buffer *VB, 
  590.                    GLuint start, GLuint count, 
  591.                    GLuint ovf )
  592. {
  593.    (void) start;
  594.    VB->CopyCount = 2;
  595.    VB->Copy[1] = count-2;
  596.    VB->Copy[2] = count-1;
  597.  
  598.    if (ovf == 1) {
  599.       VB->CopyCount = 3;
  600.       VB->Copy[0] = count-3;
  601.    }
  602. }
  603.  
  604. static void gl_fast_copy_overflow( struct vertex_buffer *VB, 
  605.                    GLuint start, 
  606.                    GLuint count,
  607.                    GLuint ovf )
  608. {
  609.    GLuint src_offset = count - ovf;
  610.    GLuint dst_offset = 3 - ovf;
  611.    GLuint i;
  612.    (void) start;
  613.    VB->CopyCount = ovf;
  614.    for (i = 0 ; i < ovf ; i++) 
  615.       VB->Copy[i+dst_offset] = i+src_offset;
  616. }
  617.  
  618.  
  619. typedef void (*fast_copy_func)( struct vertex_buffer *VB, 
  620.                 GLuint start, 
  621.                 GLuint count,
  622.                 GLuint ovf );
  623.  
  624.  
  625.  
  626.  
  627. typedef GLuint (*cull_func)( struct vertex_buffer *VB, 
  628.                  GLuint start,
  629.                  GLuint count,
  630.                  GLuint parity,
  631.                  CONST GLfloat (*proj)[4]);
  632.  
  633.  
  634. typedef GLuint (*copy_func)( struct vertex_buffer *VB, 
  635.                  GLuint start, 
  636.                  GLuint end,
  637.                  GLuint ovf,
  638.                  CONST GLfloat (*proj)[4] );
  639.  
  640.  
  641.  
  642. static cull_func cull_tab_both[GL_POLYGON+2] = 
  643. {
  644.    gl_cull_points,
  645.    gl_cull_lines,
  646.    gl_cull_line_loop,
  647.    gl_cull_line_strip,
  648.    gl_cull_triangles,
  649.    gl_cull_triangle_strip,
  650.    gl_cull_triangle_fan,
  651.    gl_cull_quads,
  652.    gl_cull_quad_strip,
  653.    gl_cull_triangle_fan,
  654.    gl_cull_dummy_prim
  655. };
  656.  
  657. static cull_func cull_tab_area[GL_POLYGON+2] = 
  658. {
  659.    gl_cull_points_neither,
  660.    gl_cull_points_neither,
  661.    gl_cull_points_neither,
  662.    gl_cull_points_neither,
  663.    gl_cull_triangles_area,
  664.    gl_cull_triangle_strip_area,
  665.    gl_cull_triangle_fan_area,
  666.    gl_cull_quads_area,
  667.    gl_cull_quad_strip_area,
  668.    gl_cull_triangle_fan_area,
  669.    gl_cull_dummy_prim
  670. };
  671.  
  672. static cull_func cull_tab_clip[GL_POLYGON+2] = 
  673. {
  674.    gl_cull_points,
  675.    gl_cull_lines,
  676.    gl_cull_line_loop,
  677.    gl_cull_line_strip,
  678.    gl_cull_triangles_clip,
  679.    gl_cull_triangle_strip_clip,
  680.    gl_cull_triangle_fan_clip,
  681.    gl_cull_quads_clip,
  682.    gl_cull_quad_strip_clip,
  683.    gl_cull_triangle_fan_clip,
  684.    gl_cull_dummy_prim
  685. };
  686.  
  687. static cull_func *cull_tab[4] = 
  688. {
  689.    0,
  690.    cull_tab_area,
  691.    cull_tab_clip,
  692.    cull_tab_both
  693. };
  694.  
  695.  
  696. static copy_func copy_tab_cull[GL_POLYGON+2] = 
  697. {
  698.    0,
  699.    gl_copy_overflow_cull,
  700.    gl_copy_first_and_last_cull,
  701.    gl_copy_last_cull,
  702.    gl_copy_overflow_cull,
  703.    gl_copy_last_two_cull,
  704.    gl_copy_first_and_last_cull,
  705.    gl_copy_overflow_cull,
  706.    gl_copy_last_two_cull,
  707.    gl_copy_first_and_last_cull,
  708.    0,
  709. };
  710.  
  711.  
  712. static copy_func copy_tab_no_cull[GL_POLYGON+2] = 
  713. {
  714.    0,
  715.    gl_copy_overflow,
  716.    gl_copy_first_and_last,
  717.    gl_copy_last,
  718.    gl_copy_overflow,
  719.    gl_copy_last_two,
  720.    gl_copy_first_and_last,
  721.    gl_copy_overflow,
  722.    gl_copy_last_two,
  723.    gl_copy_first_and_last,
  724.    0,
  725. };
  726.  
  727.  
  728. static fast_copy_func fast_copy_tab[GL_POLYGON+2] = 
  729. {
  730.    gl_fast_copy_noop,
  731.    gl_fast_copy_overflow,
  732.    gl_fast_copy_first_and_last,
  733.    gl_fast_copy_last,
  734.    gl_fast_copy_overflow,
  735.    gl_fast_copy_last_two,
  736.    gl_fast_copy_first_and_last,
  737.    gl_fast_copy_overflow,
  738.    gl_fast_copy_last_two,
  739.    gl_fast_copy_first_and_last,
  740.    gl_fast_copy_noop,
  741. };
  742.  
  743.  
  744.  
  745.  
  746.  
  747. /* Do this after (?) primitive fixup on buffers containing unwanted
  748.  * eval coords.  No early culling will be done on these vertices (it's
  749.  * a degenerate case & not worth the code), and the vertices will be
  750.  * rendered by a special 'indirect' case in gl_render_vb.  Otherwise,
  751.  * the cullmask will force (some) transforms to skip these vertices.
  752.  */
  753. void gl_purge_vertices( struct vertex_buffer *VB )
  754. {
  755.    GLuint *flags = VB->Flag;
  756.    GLubyte *cullmask = VB->CullMask;
  757.    GLuint *indirect = VB->Indirect = VB->EltPtr->start;
  758.    GLuint *in_prim = VB->Primitive;
  759.    GLuint *out_prim = VB->IM->Primitive;
  760.    GLuint *in_nextprim = VB->NextPrimitive;
  761.    GLuint *out_nextprim = VB->IM->NextPrimitive;
  762.    GLuint count = VB->Count;
  763.    GLuint purge = VB->PurgeFlags;
  764.    GLuint next, start;
  765.    GLuint j;
  766.  
  767.    /*
  768.     */
  769.    for ( j = start = VB->CopyStart ; start < count ; start = next ) {
  770.       GLuint startj = j;
  771.       GLuint i;
  772.  
  773.       next = in_nextprim[start]; 
  774.       out_prim[j] = in_prim[start];
  775.  
  776.       for ( i = start ; i < next ; i++) {
  777.      if (~(flags[i] & purge)) {
  778.         indirect[j] = i;
  779.         cullmask[i] = PRIM_CLIPPED;    /* nonzero */
  780.         j++;
  781.      }
  782.      
  783.       }
  784.  
  785.       out_nextprim[startj] = j;
  786.    }
  787.    
  788.    VB->Primitive = out_prim;
  789.    VB->NextPrimitive = out_nextprim;
  790.    VB->IndirectCount = j;
  791. }
  792.  
  793. #define VERT_NOT_CLIPPED 0x80
  794.  
  795. static void build_clip_vert_bits( GLubyte *clipmask, const GLubyte *cullmask,
  796.                   GLuint count )
  797. {
  798.    GLuint i = 0;
  799.    for (;;)
  800.       if (cullmask[++i]==0) {
  801.      clipmask[i] |= CLIP_CULLED_BIT;
  802.      if (&cullmask[i] == &cullmask[count]) return;
  803.       }
  804. }
  805.  
  806. GLuint gl_cull_vb( struct vertex_buffer *VB )
  807. {
  808.    const GLcontext *ctx = VB->ctx;
  809.    GLuint i, next, prim, n;
  810.    GLfloat (*proj)[4] = VB->Projected->data;
  811.    GLuint *in_prim = VB->Primitive;
  812.    GLuint *out_prim = VB->IM->Primitive;
  813.    GLuint cullcount = 0;
  814.    GLuint lastprim = in_prim[VB->LastPrimitive];
  815.    GLuint first = VB->CopyStart;
  816.    GLuint parity = VB->Parity;
  817.    cull_func *cull_funcs;
  818.    GLuint idx = 0;
  819.  
  820.    if (VB->CullDone)
  821.       return 0;
  822.  
  823.    if (VB->ClipOrMask)
  824.       idx |= 0x2;
  825.  
  826.    if (ctx->IndirectTriangles & DD_ANY_CULL)
  827.       idx |= 0x1;
  828.    
  829.    cull_funcs = cull_tab[idx];
  830.  
  831.    for (i = VB->CopyStart ; i < VB->Start ; i++) {
  832.       COPY_4FV(proj[i], VB->CopyProj[i]);
  833.    }
  834.  
  835.    VB->CopyCount = 0;
  836.  
  837.    MEMSET(VB->CullMask, 0, (VB->Count+1) * sizeof(GLubyte));
  838.  
  839.    for ( i = VB->CopyStart ; i < VB->Count ; i = next, parity = 0 ) 
  840.    {
  841.       first = i;
  842.       next = VB->NextPrimitive[i];
  843.       prim = in_prim[i];
  844.       n = cull_funcs[prim]( VB, i, next, parity, (const GLfloat (*)[4])proj );
  845.  
  846.       if (n == next - i)
  847.      out_prim[i] = GL_POLYGON+1; 
  848.       else 
  849.      out_prim[i] = prim;
  850.  
  851.       cullcount += n;
  852.    }
  853.  
  854.  
  855.    if (VB->LastPrimitive <  VB->Count) {
  856.       if (copy_tab_cull[lastprim]) 
  857.      cullcount -= copy_tab_cull[prim]( VB, 
  858.                        first, 
  859.                        VB->Count, 
  860.                        VB->Ovf, 
  861.                        (const GLfloat (*)[4])proj );     
  862.    }
  863.  
  864.    VB->Primitive = out_prim;
  865.    
  866.    VB->CullFlag[0] = VB->CullFlag[1] = (GLubyte) 0;
  867.  
  868.    if (cullcount > 0 || (ctx->IndirectTriangles & DD_LIGHTING_CULL)) {
  869.       VB->CullMode |= CULL_MASK_ACTIVE;
  870.       VB->CullFlag[0] = VB->CullFlag[1] = CLIP_CULLED_BIT&ctx->AllowVertexCull;
  871.  
  872.       if (cullcount < VB->Count)
  873.      build_clip_vert_bits( VB->ClipMask, VB->CullMask, VB->Count );
  874.  
  875.    }
  876.    if (VB->ClipOrMask) {
  877.       VB->CullMode |= CLIP_MASK_ACTIVE;
  878.       VB->CullFlag[1] |= (CLIP_ALL_BITS|CLIP_USER_BIT) & ctx->AllowVertexCull; 
  879.    }
  880.  
  881.    VB->CullDone = 1;
  882.    return cullcount;
  883. }
  884.  
  885.  
  886. /* Need to set up to copy some vertices at the end of the buffer, even
  887.  * if culling is disabled or the entire vb has been culled by clipping.
  888.  */
  889. void gl_dont_cull_vb( struct vertex_buffer *VB )
  890. {
  891.    GLfloat (*proj)[4] = VB->Projected->data;
  892.    GLuint i;
  893.  
  894.    if (VB->CullDone)
  895.       return;
  896.  
  897.    for (i = VB->CopyStart ; i < VB->Start ; i++) 
  898.       COPY_4FV(proj[i], VB->CopyProj[i]);
  899.    
  900.    VB->CopyCount = 0;
  901.  
  902.    if (VB->LastPrimitive < VB->Count) 
  903.    {
  904.       GLuint first = VB->LastPrimitive;
  905.       GLuint prim = VB->Primitive[first];
  906.  
  907.       if (first == VB_START)
  908.      first = VB->Start;
  909.  
  910.       if (copy_tab_no_cull[prim]) 
  911.      copy_tab_no_cull[prim]( VB, 
  912.                  first, 
  913.                  VB->Count, 
  914.                  VB->Ovf,
  915.                  (const GLfloat (*)[4])proj );
  916.    }
  917.  
  918.    VB->CullDone = 1;
  919. }
  920.  
  921. void gl_fast_copy_vb( struct vertex_buffer *VB )
  922. {
  923.    VB->CopyCount = 0;
  924.  
  925.    if (VB->LastPrimitive < VB->Count) 
  926.    {
  927.       GLuint first = VB->LastPrimitive;
  928.       GLuint prim = VB->Primitive[first];
  929.  
  930.       if (first == VB_START) 
  931.      first = VB->Start;
  932.  
  933.       fast_copy_tab[prim]( VB, first, VB->Count, VB->Ovf );
  934.    }
  935.  
  936.    VB->CullDone = 1;
  937. }
  938.  
  939.  
  940.  
  941.  
  942.  
  943. void gl_make_normal_cullmask( struct vertex_buffer *VB )
  944. {
  945.    GLuint i;
  946.  
  947.    if (VB->CullMode & COMPACTED_NORMALS) {
  948.       /* The shared normals case - never for cva.
  949.        */
  950.       MEMSET(VB->NormCullMask, 0, VB->Count * sizeof(GLubyte));      
  951.       VB->NormCullStart = VB->NormCullMask + VB->Start;
  952.  
  953.       if (VB->CullMode & CULL_MASK_ACTIVE) {
  954.      GLubyte *lastnorm = VB->NormCullStart;
  955.  
  956.      for (i = VB->Start ;;) {
  957.         *lastnorm |= VB->CullMask[i];
  958.         if (VB->Flag[++i] & (VERT_NORM|VERT_END_VB)) {
  959.            lastnorm = &VB->NormCullMask[i];
  960.            if (VB->Flag[i] & VERT_END_VB) return;
  961.         }
  962.      }
  963.       } else {
  964.      VB->NormCullMask[VB->Start] = ~0;
  965.      for (i = VB->Start ;; ) 
  966.         if (VB->Flag[++i] & (VERT_NORM|VERT_END_VB)) {
  967.            VB->NormCullMask[i] = ~0;
  968.            if (VB->Flag[i] & VERT_END_VB) return;
  969.         }
  970.       }
  971.    } else  {
  972.       /*  Non-shared normals.
  973.        */
  974.       VB->NormCullStart = VB->CullMask + VB->Start;      
  975.    }   
  976. }
  977.  
  978.  
  979.  
  980.  
  981.