From: hgn <hgodden00@gmail.com>
Date: Thu, 7 Apr 2022 02:26:31 +0000 (+0100)
Subject: displacement detection
X-Git-Url: https://harrygodden.com/git/?p=convexer.git;a=commitdiff_plain;h=730fbd0939c0f334b40840a1e97757f642366448

displacement detection
---

diff --git a/__init__.py b/__init__.py
index 6639af1..0e4ddd2 100644
--- a/__init__.py
+++ b/__init__.py
@@ -117,7 +117,8 @@ class cxr_polygon(Structure):
 
 class cxr_edge(Structure):
    _fields_ = [("i0",c_int32),
-               ("i1",c_int32)]
+               ("i1",c_int32),
+               ("freestyle",c_int32)]
 
 class cxr_material(Structure):
    _fields_ = [("res",c_int32 * 2),
@@ -850,6 +851,7 @@ def mesh_cxr_format(obj):
    for i, edge in enumerate(data.edges):
       edge_data[i].i0 = edge.vertices[0]
       edge_data[i].i1 = edge.vertices[1]
+      edge_data[i].freestyle = edge.use_freestyle_mark
 
    material_data = (cxr_material*len(obj.material_slots))()
 
diff --git a/src/convexer.c b/src/convexer.c
index 7669e97..ed04caf 100644
--- a/src/convexer.c
+++ b/src/convexer.c
@@ -103,6 +103,7 @@ struct cxr_input_mesh
    struct cxr_edge
    {
       i32 i0, i1;
+      i32 freestyle;
    }
    *edges;
 
@@ -473,8 +474,17 @@ static void cxr_mesh_clean_edges(struct cxr_mesh *mesh)
          struct cxr_edge edge = { i0, i1 };
          // --- ! ---
          // Copy extra information (sharp,freestyle.. etc) here!
-         //
-         // if orig_edge_id < mesh->edges.count: edge.foo = mesh->edges[orig].foo
+
+         if( orig_edge_id < mesh->edges.count )
+         {
+            struct cxr_edge *orig_edge = cxr_ab_ptr( &mesh->edges, orig_edge_id );
+            edge.freestyle = orig_edge->freestyle;
+         }
+         else
+         {
+            edge.freestyle = 0;
+         }
+
          // --- ! ---
          cxr_ab_push( &new_edges, &edge );
 
@@ -1771,6 +1781,459 @@ CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src)
    return NULL;
 }
 
+// Convert contiguous mesh to patch of displacments
+//
+static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_vdf *output, 
+   struct cxr_auto_buffer *abverts)
+{
+   // Create a graph which maps vertices by their connections
+   struct vertinfo
+   {
+      int con_start, con_count;     // Index into the connection graph
+      int boundary,
+          used,
+          search,
+          corner;
+
+      double alpha;
+   }
+   *vertinfo = malloc( sizeof(struct vertinfo)*abverts->count );
+   int *graph = malloc( sizeof(int) * mesh->edges.count*2 );
+   
+   int con_pos = 0;
+   for( int i=0; i<abverts->count; i++ )
+   {
+      struct vertinfo *info = &vertinfo[i];
+      info->con_start = con_pos;
+      info->con_count = 0;
+      info->boundary = 0;
+      info->corner = 0;
+      info->used = 0;
+      info->search = 0;
+      info->alpha = 0.0;
+
+      for( int j=0; j<mesh->edges.count; j++ )
+      {
+         struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,j);
+
+         if( edge->i0 == i || edge->i1 == i )
+         {
+            graph[ con_pos ++ ] = edge->i0 == i? edge->i1: edge->i0;
+            info->con_count ++;
+
+            if( edge->freestyle )
+               info->boundary = 1;
+         }
+      }
+   }
+
+   // Find best normal for brush patch. VBSP uses the original brush
+   // as reference for decal projection.
+   //
+   // These are clamped to be cardinal directions as to make the VMF somewhat
+   // human editable.
+
+   v3f avg_normal;
+   
+   for( int i=0; i<mesh->polys.count; i++ )
+   {
+      struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i );
+      v3_add( poly->normal, avg_normal, avg_normal );
+   }
+   v3_divs( avg_normal, mesh->polys.count, avg_normal );
+   v3_normalize( avg_normal );   // TODO: This can be zero length. Should add a safety check
+                                 // normalize function that checks for small length before
+                                 // carrying out, otherwise we get inf/nan values...
+   
+   double component_max = fabs( avg_normal[2] );
+   int component = 2;
+
+   for( int i=0; i<2; i++ )
+   {
+      if( fabs(avg_normal[i]) > component_max )
+      {
+         component_max = fabs(avg_normal[i]);
+         component = i;
+      }
+   }
+   double d = avg_normal[component] >= 0.0? 1.0: -1.0;
+   v3_zero( avg_normal );
+   avg_normal[component] = d;
+   
+   // Approximately matching the area of the result brush faces to the actual area
+   // this is to assign a 'best guess' amount of lightmap texels.
+   //
+   double uv_area = 0.0, face_area = 0.0, sf;
+   
+   for( int i=0; i<mesh->polys.count; i++ )
+   {
+      struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i );
+
+      for( int j=0; j<poly->loop_total-2; j++ )
+      {
+         struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start),
+                         *lp1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+1),
+                         *lp2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+2);
+         v3f va, vb, orth;
+         v3_sub( cxr_ab_ptr(abverts,lp1->index), cxr_ab_ptr(abverts,lp0->index), va );
+         v3_sub( cxr_ab_ptr(abverts,lp2->index), cxr_ab_ptr(abverts,lp0->index), vb );
+         v3_cross( va, vb, orth );
+         
+         face_area += v3_length( orth ) / 2.0;
+         
+         v2f uva, uvb;
+         v2_sub( lp1->uv, lp0->uv, uva );
+         v2_sub( lp2->uv, lp0->uv, uvb );
+         
+         uv_area += fabs(v2_cross( uva, uvb )) / 2.0;
+      }
+   }
+
+   sf = sqrt( face_area / uv_area );
+   int corner_count = 0;
+
+   // Vertex classification
+   for( int i=0; i<abverts->count; i++ )
+   {
+      struct vertinfo *info = &vertinfo[i];
+      if( !info->boundary ) continue;
+
+      int count = 0,
+          non_manifold = 1;
+
+      for( int j=0; j<info->con_count; j++ )
+      {
+         int con = graph[info->con_start+j];
+
+         if( vertinfo[con].boundary )
+            count ++;
+         else
+            non_manifold = 0;
+      }
+      if( count > 2 || non_manifold )
+      {
+         info->corner = 1;
+         corner_count ++;
+
+         //cxr_debug_box( cxr_ab_ptr(abverts,i), 0.1, colour_success );
+      }
+   }
+   
+   int dispedge[16];
+   v2f corner_uvs[4];
+   int dispedge_count;
+   int disp_count = 0;
+
+   for( int i=0; i<mesh->polys.count; i++ )
+   {
+      struct cxr_polygon *basepoly = cxr_ab_ptr(&mesh->polys,i);
+
+      for( int h=0; h<basepoly->loop_total; h ++ )
+      {
+         int i0 = h,
+             i1 = cxr_range(h+1,basepoly->loop_total);
+
+         struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i0),
+                         *l1 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i1);
+         struct vertinfo *info = &vertinfo[ l0->index ];
+
+         if( info->corner )
+         { 
+            int corner_count = 1;
+
+            dispedge_count = 2;
+            dispedge[0] = l0->index;
+            dispedge[1] = l1->index;
+            v2_copy( l0->uv, corner_uvs[0] );
+            
+            // Consume (remove) faces we use for corners
+            basepoly->loop_total = -1;
+
+            cxr_debug_box( cxr_ab_ptr(abverts,l0->index),0.08,(v4f){0.0,0.0,1.0,1.0});
+            disp_count ++;
+
+            // Collect edges 
+            // --------------------
+
+            while( dispedge_count < 17 )
+            {
+               struct vertinfo *edge_head = &vertinfo[dispedge[dispedge_count-1]];
+               int newvert = 0;
+               
+               if( edge_head->corner )
+               {
+                  // Find a polygon that has the edge C-1 -> C
+                  for( int j=0; j<mesh->polys.count && !newvert; j++ )
+                  {
+                     struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
+
+                     for( int k=0; k<poly->loop_total; k ++ )
+                     {
+                        int i0 = k,
+                            i1 = cxr_range(k+1,poly->loop_total);
+
+                        struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i0),
+                                        *l1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i1);
+
+                        if( l0->index == dispedge[dispedge_count-2] &&
+                            l1->index == dispedge[dispedge_count-1] )
+                        {
+                           // Take the vertex after that edge
+                           v2_copy( l1->uv, corner_uvs[corner_count ++] );
+
+                           int i2 = cxr_range(i1+1,poly->loop_total);
+                           struct cxr_loop *l2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i2);
+
+                           dispedge[dispedge_count ++] = l2->index;
+                           newvert = 1;
+                           poly->loop_total = -1;
+                           break;
+                        }
+                     }
+                  }
+               }
+               else
+               {
+                  for( int j=0; j<edge_head->con_count; j++ )
+                  {
+                     int con = graph[edge_head->con_start+j];
+
+                     if( con == -1 )
+                        continue;
+
+                     if( dispedge_count > 1 )
+                        if( con == dispedge[dispedge_count-2] )
+                           continue;
+                     
+                     struct vertinfo *coninfo = &vertinfo[con];
+                     
+                     if( !coninfo->boundary )
+                        continue;
+
+                     cxr_debug_arrow( cxr_ab_ptr(abverts,dispedge[dispedge_count-1]),
+                                      cxr_ab_ptr(abverts,con),
+                                      (v3f){0,0,1},
+                                      0.1,
+                                      colour_success );
+
+                     dispedge[ dispedge_count ++ ] = con;
+                     newvert = 1;
+
+                     break;
+                  }
+               }
+
+               if( !newvert )
+               {
+                  cxr_debug_box(cxr_ab_ptr(abverts,dispedge[dispedge_count-1]), 0.1, colour_error);
+                  break;
+               }
+            }
+            
+            // --------------------
+            // Edges collected
+            
+            v2f va, vb;
+            v2_sub( corner_uvs[1], corner_uvs[0], va );
+            v2_sub( corner_uvs[2], corner_uvs[0], vb );
+
+            if( v2_cross( va,vb ) < 0.0 )
+               cxr_log( "Uv is flipped!\n" );
+            else
+               cxr_log( "Uv is normal\n" );
+
+            // Connect up the grid
+            //
+            //   0 1 2 3 4
+            //  15 a b c d
+            //  14 e f g h
+            //  13 i j k l
+            //  12 m n o p
+            //
+            //  Example: a := common unused vertex that is connected to
+            //                by 1 and 15. Or y-1, and x-1 on the grid.
+            //           g := c and f common vert ^
+            //
+            int grid[25];
+            
+            for( int j=0; j<25; j++ ) grid[j] = 0;
+            for( int j=0; j<5; j++ )
+            { 
+               grid[j] = dispedge[j]; 
+               vertinfo[dispedge[j]].used = 1;
+            }
+            for( int j=1; j<5; j++ )
+            {
+               grid[j*5] = dispedge[16-j];
+               vertinfo[dispedge[16-j]].used = 1;
+            }
+
+            for( int j=1; j<5; j++ )
+            {
+               for( int k=1; k<5; k++ )
+               {
+                  int s0 = grid[(j-1)*5+k],
+                      s1 = grid[j*5+k-1];
+
+                  struct vertinfo *va = &vertinfo[s0],
+                                  *vb = &vertinfo[s1];
+
+                  // Find a common vertex between s0 and s1
+                  
+                  for( int l=0; l<va->con_count; l ++ )
+                  {
+                     for( int m=0; m<vb->con_count; m ++ )
+                     {
+                        int cona = graph[va->con_start+l],
+                            conb = graph[vb->con_start+m];
+
+                        if( vertinfo[cona].used || vertinfo[conb].used )
+                           continue;
+
+                        if( cona == conb )
+                        {
+                           grid[ j*5+k ] = cona;
+                           vertinfo[cona].used = 1;
+
+                           goto IL_MATCHED_DISP_INTERIOR_VERT;
+                        }
+                     }
+                  }
+
+                  // Broken displacement
+                  cxr_log( "Broken displacement!\n" );
+                  free( graph );
+                  free( vertinfo );
+                  return;
+
+                  IL_MATCHED_DISP_INTERIOR_VERT:;
+               }
+            }
+            
+            // Release grid
+            for( int j=0; j<25; j++ )
+               vertinfo[grid[j]].used = 0;
+         }
+      }
+   }
+
+   cxr_log( "Disp count: %d\n", disp_count );
+
+   // Main loop
+#if 0
+   int pool[25];
+   for( int i=0; i<abverts->count; i++ )
+   {
+      struct vertinfo *info = &vertinfo[i];
+      if( info->boundary || info->used )
+         continue;
+
+      // Gather all vertices in this displacement
+      int poolcount = 1,
+          front_start = 0,
+          front_count = 1;
+      pool[0] = i;
+      info->used = 1;
+
+      IL_GATHER_LOOP:;
+      
+      int new_front_start = poolcount;
+
+      for( int j=0; j<front_count; j++ )
+      {
+         struct vertinfo *frontvert = &vertinfo[pool[front_start+j]];
+
+         for( int k=0; k<frontvert->con_count; k++ )
+         {
+            int conid = graph[frontvert->con_start+k];
+            struct vertinfo *con = &vertinfo[conid];
+
+            if( frontvert->boundary && !con->boundary )
+               continue;
+
+            if( con->used )
+               continue;
+            
+            if( poolcount == 25 )
+               goto IL_DISP_ERROR_COUNT;
+
+            con->used = 1;
+            pool[ poolcount ++ ] = conid;
+         }
+      }
+
+      if( poolcount > new_front_start )
+      {
+         front_start = new_front_start;
+         front_count = poolcount-front_start;
+
+         goto IL_GATHER_LOOP;
+      }
+      
+      if( poolcount != 25 )
+      {
+IL_DISP_ERROR_COUNT:
+         for( int i=0; i<poolcount; i++ )
+            cxr_debug_box( cxr_ab_ptr(abverts,pool[i]), 0.02, colour_error );
+
+         free(graph);
+         free(vertinfo);
+
+         cxr_log("Invalid displacement (>25 verts)\n");
+         return;
+      }
+
+      int corners[4];
+      int corner_count = 0;
+      struct cxr_loop *cornerloops[4];
+      
+      // Find corners, and get their loops (for uvs)
+      // note: the mesh must be split where there is texture seams
+      //       so that two different uv'd loops cant ref the same vertex
+      //
+      for( int j=0; j<poolcount; j++ )
+      {
+         if( vertinfo[pool[j]].corner )
+         {
+            if( corner_count == 4 )
+            {
+               corner_count = -1;
+               break;
+            }
+
+            corners[corner_count] = j;
+            
+            // find loop that includes this vert
+            for( int k=0; k<mesh->loops.count; k++ )
+            {
+               struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,k);
+               if( lp->index == pool[j] )
+               {
+                  cornerloops[corner_count] = lp;
+                  break;
+               }
+            }
+
+            corner_count ++;
+         }
+      }
+
+      if( corner_count !=4 )
+      {
+         free(graph);
+         free(vertinfo);
+         cxr_log( "Invalid displacement (!=4 corners)\n" );
+         return;
+      }
+
+      int pivot = corners[0];
+   }
+#endif
+
+   free( graph );
+   free( vertinfo );
+}
+
 CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *output)
 {
    // Split mesh into islands
@@ -1808,6 +2271,30 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *
    
    // Preprocessor 2: Displacement break-out
    //  ---------------
+   for( int i=0; i<solids.count; i++ )
+   {
+      struct solidinf *pinf = cxr_ab_ptr(&solids,i);
+      
+      for( int j=0; j<pinf->pmesh->polys.count; j++ )
+      {
+         struct cxr_polygon *poly = cxr_ab_ptr( &pinf->pmesh->polys, j );
+
+         for( int k=0; k<poly->loop_total; k++ )
+         {
+            struct cxr_loop *lp = cxr_ab_ptr( &pinf->pmesh->loops, poly->loop_start+k );
+            struct cxr_edge *edge = cxr_ab_ptr( &pinf->pmesh->edges, lp->edge_index );
+
+            if( edge->freestyle )
+               goto IL_SOLID_IS_DISPLACEMENT;
+         }
+      }
+      
+      continue;
+      IL_SOLID_IS_DISPLACEMENT:;
+      
+      pinf->is_displacement = 1;
+      cxr_write_disp( pinf->pmesh, output, &abverts );
+   }
 
    // Preprocessor 3: Breakup non-convex shapes into sub-solids
    //  ---------------
@@ -1818,7 +2305,6 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *
       struct solidinf pinf = *(struct solidinf *)cxr_ab_ptr(&solids, i);
 
       if( pinf.is_displacement )
-         // TODO: write displacements here... 
          continue;
 
       while(1)
@@ -1859,7 +2345,9 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *
       for( int i=0; i<solids.count; i++ )
       {
          struct solidinf *solid = cxr_ab_ptr(&solids,i);
-         cxr_debug_mesh( solid->pmesh, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
+
+         if( !solid->is_displacement )
+            cxr_debug_mesh( solid->pmesh, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
       }
    }