# Question
Title: Normal map lighting is just slightly off
I've been trying to implement normal mapping into my custom OpenGL shader. The result I'm getting is *almost* there, but it looks like the `Point Light` is not illuminating the mesh evenly.

For context, I recently added lighting, added a `Point Light` and a rectangle with a texture to do regular lighting and got this result:

This is a desired result, the `Point Light` (it's the small yellow cube above the rectangle) illuminates the rectangle with the brick texture evenly.

I then wanted to add a normal map, so instead of using the vertex normals, I'd use normals from another texture. The result I'm getting is this:

The result is *almost* there, the normal map is being applied, and the bricks almost look 3D. The only problem is that one corner of the mesh remains dark, even though the light is exactly in the middle of the rectangle, so I'd expect the illumination to be even.

In case it helps, here's a gif that shows the Point Light moving in an `8` pattern above the rectangle:

My current attempt is to get the normals from the normal map and convert them from Tangent Space to View Space (where the lighting takes effect already).

Here is the `Vertex Shader` I'm using:

```
// vertex attributes
in vec3 colour;
in vec3 normal;
in vec2 texCoord;
in vec3 tangent;
in vec3 bitangent;

// output to fragment shader
out vec4 outColour;
out vec2 outTexCoord;
out vec3 outNormal_view;
out vec3 outLightPos_view;
out vec3 outPos_view;
out mat3 outTBN;

// light position in global space
uniform vec3 lightPos;

void main() {
    // vertex positions
    vec4 pos = matrix_projection *matrix_view *matrix_model *position;
    gl_Position = pos;

    // convert light and vertex positions to view space and pass them to fragment shader
    vec3 lightPos_view = vec3((matrix_view *vec4(lightPos, 1.0)).rgb);
    vec3 pos_view = vec3(matrix_view *matrix_model *position);
    outLightPos_view = lightPos_view;
    outPos_view = pos_view;

    // convert vertex normals to view spacce and pass them to fragment shader
    vec3 normal_world = mat3(transpose(inverse(matrix_view *matrix_model))) *normal.rgb;
    outNormal_view = normal_world;

    // TBN matrix to convert normals from tangent space to view space
    vec3 normal_view    = normalize( vec3(matrix_view *matrix_model * vec4(normal   , 0.0)) );
    vec3 tangent_view   = normalize( vec3(matrix_view *matrix_model * vec4(tangent  , 0.0)) );
    vec3 bitangent_view = normalize( vec3(matrix_view *matrix_model * vec4(bitangent, 0.0)) );
    mat3 TBN = mat3( tangent_view, bitangent_view, normal_view );
    outTBN = TBN;

    outColour = vec4(colour.rgb, 1.0);

    outTexCoord = texCoord;
}

```

And here is the `Fragment Shader`:

```
// input from vertex shader
in vec4 outColour;
in vec2 outTexCoord;
in vec3 outNormal_view;
in vec3 outLightPos_view;
in vec3 outPos_view;
in mat3 outTBN;

// texture and it's normal map
uniform sampler2D image;
uniform sampler2D image_normal;

void main() {

    // normals from texture to view space
    vec3 norm = avdl_texture(image_normal, outTexCoord).rgb;
    norm = normalize(norm * 2.0 - 1.0);
    norm = normalize(outTBN *norm);

    // light values in view space
    vec3 lightColour = vec3(1.0, 1.0, 1.0);
    vec3 lightDir = normalize(outLightPos_view -outPos_view.rgb);

    // `outNnormal_view` is using vertex normals and it works
    // `norm` is using normal map normals, and it shows the dark corner
    vec3 normal_view = outNormal_view;
    //vec3 normal_view = norm;
    float diff = max(dot(normal_view.rgb, lightDir), 0.0);
    vec3 diffuse = diff * lightColour;

    gl_FragColor = vec4(outColour.rgb *diffuse, 1.0) *texture2D(image, outTexCoord);

}

```

I'm still learning, but I can confirm in this specific scenario, the rectangle vertices have the Normal `(0, 1, 0)`, Tangent `(1, 0, 0)` and Bitangent `(0, 0, 1)`. From what I understand this is how they should look like on a flat surface that points up, but I'm not sure if I'm messing something up in the `TBN` calculations.

For reference, I've been using the tutorial from here: https://learnopengl.com/Advanced-Lighting/Normal-Mapping \- the texture and normal map were taken directly from there, for learning purposes.

# Answer
> 0 votes
Unsurprisingly I missed something that was throwing all the normal calculations off. I recently added gamma correction into my renderer, so the following line:

```
vec3 norm = avdl_texture(image_normal, outTexCoord).rgb;`

```

Returns the normal in Linear Space. All I needed to do is convert that to sRGB space with the following lines:

```
float gamma = 2.2;
norm = pow(norm.rgb, vec3(1.0/gamma));

```

After that, all the rest of the calculations do the trick, and this is the result I'm getting:

---
Tags: opengl, shaders, lighting, normal-mapping, bump-map
---


# Question
Title: How can I structure my game like a "classical" program?
How can I setup a Godot 4 project in the way of a "classical" software project? With a `Main` function. Openable in *any* IDE. Compiling to an executable file to which I may attach any debugger or profiler fitting my compiler. With visible, traceable data and control flows.

I have found documentation indicating that I should extend a MainLoop but that documentation seems to be... confused? I do not think it is talking about the same thing:

* "Upon the application start, a MainLoop implementation must be provided to the OS; otherwise, the application will exit." - no. The OS calls `Main`. As long as `Main` does not return or throw, nothing will exit (well, the OS could of course kill the process, but will not do such a thing normally; but then, if the application previously forked additional processes, losing the first one will not necessarily shut down the whole application).
* "godot -s my\_loop.gd" - no. This is not how to start a C# application, nor a call to a C# compiler.
(I guess it's fine for trying out an isolated part of the program, like e.g. a test runner for xUnit, but we are talking about the *Main Loop* here - not many "isolated parts" left when running the Main Loop!)

*Alternatively, if this is not possible* : How can I debug effects seen in the WYSIWYG editor (such as the sprite animation state machine) without lines of code for breakpoints and without fields for watch points? Using a normal debugger for the language chosen, e.g. the Visual Studio debugger or the Jetbrains Rider debugger or even lldb?

... I have been a programmer for decades now, including for games, but (or maybe thence?) I cannot seem to wrap my head around working with these "Game Engines" in particular. Previously I have given up on Unreal and Unity, now I am trying Godot, but the problem is always the same: They take away all my tools and give lots and lots of... inadequate, indirect, immature, inferior replacements. I just hope it is a matter of unmatching vocabulary (that is: I am using the wrong terms for this domain) or similar misunderstandings and easily resolved.

# Answer
## Finding the entry point in Godot

Godot has a different entry point and uses different binding for each platform it supports. Because of that, it does not offer access to any of the actual entry point functions. Thus, if you want to do this with Godot you would be working with the source code, i.e. clone the repository. See Building from source.

In fact, Godot supports two approaches to develop your games in C++ (Modules and GDExtension) beside modifying the source code.

Of course, you can modify the source. My answer to How is the Godot Engine itself structured? might help you get around.

---

## Using Godot as a library

If your goal is just to retain control of the entry point, consider for example SwiftGodot which allows you to take control of Godot as if it were a library (something that has been proposed for the engine, but has no official support).

---

## Debug your game on Visual Studio Code

I also want to highlight that even though the GDScript debugger is built-in inside Godot, you can connect to via socket since it launches a debug server over the loopback adapter. In fact Godot-Tools plugin for Visual Studio Code connects to it this way, allows you to debug GDScript from Visual Studio Code. Similar plugins for other IDEs should be possible (although I'm not aware of any). If you also want to debug C# from Godot inside of Visual Studio Code you can use C# Tools for Godot.

---

## Godot development (as in developing the engine, not a game on the engine)

Let us say found a bug in Godot and want to fix it yourself. Even in this scenario it remains a good idea to report it, as the developers expect either an issue or a proposal to justify any pull request. See the Pull request workflow.

Of course the contributors need to debug the engine, which is different from debugging the games. In Building from source you also find how to make debug builds. And, of course, Godot is a C++ application, which you would debug with a suitable C++ debugger.

There is also a contributors chat where you can find help when working on improving the engine.

---

## On other engines

And yes, it is the similar situation with any Game Engine in that they hide the entry point (and arguably worse if you don't have access to the source code). Which makes me think you want a game development framework that is not a Game Engine.

So, I would like to submit these to your consideration: The Best Game Development Frameworks. *Of course this is not an exhaustive list, and it is bound to be outdated, but I hope it help you find a better fit tool.*

---

To be fair, if debugging the games is enough, if I recall correctly the integration of C# in both Unity and Godot allows debugging with an external .NET debugger.
> 15 votes

# Answer
With modern engines such as Unity and Unreal, the engine is far more than just a library of code that you build onto. It might help to think of it this way: you're not developing a full application, you're developing *content* that runs in the engine. Your content will almost certainly include custom code, but the content in and of itself isn't a full application. Depending on the engine and licensing terms, you may or may not have access to the source code for the engine and editing tools, but you're generally not expected to need to debug the tools, just like you wouldn't expect to need to run a debugger or step through the source code when authoring content with software such as Word, Photoshop, Final Cut Pro, or Pro Tools.

On that note, video editing software is a good analogy for how to think about these engines:

* With video editing software, you'll create a project into which you import assets (video clips, audio clips, and images). You create content from these assets (by arranging them on a timeline). You can export your content (as a video file) and run it in compatible software (a media player).
* With a game engine that comes with development tools/software, you'll create a project into which you import assets (code, models, textures, audio, etc). You create content from these assets (by building scenes/levels/etc). You can export your content (as some combination of binary and text data) and it runs in compatible software (the engine executable).

For the purposes of the analogy, the biggest difference here is that a video file is standalone content that can be viewed in different media playing software, whereas a game typically ships with an engine executable and only runs in that specific executable.

With video editing software, you wouldn't expect to need to run the video editor in a debugger or step through its source code. You don't need to worry about the specifics of how the video is played, or what platform it's viewed on\*. You just focus on authoring your content.

If you look at developing in a typical modern engine with the same perspective, it starts to make more sense. The engine is designed to handle low-level things (like interfacing with the operating system, and initializing core modules) so you can focus on creating unique content for your game. The GUI-driven editing tools/software are designed to be usable by people who aren't programmers and without the need for debugging. Yes, the tools can have bugs, but so can any other software you don't have access to the source for.

**In reality, you do sometimes need to worry about things like what codecs and bitrates are supported on a particular target device, but that's too much of a tangent.*

---

Let's look at part of what you wrote:

> "Upon the application start, a MainLoop implementation must be provided to the OS; otherwise, the application will exit." - no. The OS calls Main. As long as Main does not return or throw, nothing will exit

The wording here is definitely confusing, but `MainLoop` is not the `main()` function called by the operating system. Your implementation of `MainLoop` is part of your *content* that runs within the engine.

If you want to see the built-in engine code that runs when Godot starts, try here: https://github.com/godotengine/godot/blob/master/main/main.cpp. If you search that code, you can see how the MainLoop gets initialized
> 10 votes

# Answer
Good, general answers already here. I'll just add a little Godot-specific information. One of the reasons why there isn't an alternative IDE for Godot (nor indeed is it likely for there to ever be one) is that a LOT (sometimes even most) of the development actually happens inside the custom "TSCN" (Scene) files. These files are not code but more like configuration. It's what ties all the separate pieces of content together into a coherent game. Their editor is the visual editor you have on the screen. Replicating that in another IDE would mean recreating most of Godot itself. There's just no point.

You can however use an external IDE for the code parts that you write for the game, if you choose to use C#. But, just to reiterate - that code will be just a part of your game, and might not even be the biggest part. It will just cover the hyper-specific parts of the game that are not already part of the engine. Most of the generic stuff (graphics, physics, collisions, etc) will be handled by the Godot engine itself, and set up via the TSCN files.

Remember - the point of Godot and other engines is to REDUCE the amount of code you need to write (up to eliminating it entirely in some cases), so they provide a vast set of tools and libraries to take as much work away from you as possible.

And don't forget that they are "frameworks" rather than "libraries". By that I mean:

* A "library" provides a set of useful functions that you may or may not use in your program as you see fit. But you're in control of your own program and its structure.
* A "framework" provides a program structure which you extend at predefined points.
> 2 votes

---
Tags: c#, godot, godot-4
---


# Question
Title: Generate ETC2 compressed texture from Android Bitmap in OpenGL ES 2
My app currently uses a lot of textures most of which probably could be compressed quite a lot by using ETC2 (my app runs on 4.4 so i have a lot of devices supporting GLES30), i cannot use ETC1 since i need alpha too.

Problem is that i map my textures from a Bitmap i create dynamically (and quite often every 60 seconds), i currently map them this way (textures are not power of 2 sized):

```
GLES20.glBindTexture(GLES20.GL_TEXTURE_2D, id);
GLES20.glTexParameteri(GLES20.GL_TEXTURE_2D, GLES20.GL_TEXTURE_MIN_FILTER, GLES20.GL_LINEAR);
GLES20.glTexParameteri(GLES20.GL_TEXTURE_2D, GLES20.GL_TEXTURE_MAG_FILTER, GLES20.GL_LINEAR);
GLES20.glTexParameteri(GLES20.GL_TEXTURE_2D, GLES20.GL_TEXTURE_WRAP_S, mode);
GLES20.glTexParameteri(GLES20.GL_TEXTURE_2D, GLES20.GL_TEXTURE_WRAP_T, mode);
GLUtils.texImage2D(GLES20.GL_TEXTURE_2D, 0, bitmap, 0);

```

So i was wondering if:

* Is it possible to load a Bitmap using ETC2 to use less memory on the graphic card? A code example would be great
* How much overhead does the compression have? Mapping a 1024x1024 ARGB\_8888 Bitmap every 60 seconds is feasible?

# Answer
> 2 votes
Note that while GLES3 mandates ETC2 support, it doesn't mandate that it saves any memory on the graphics card. A lot of implementations that support it simply decompresses the texture in software and create an uncompressed texture on the graphics card. The same problem also applies to ASTC.

If you need a format that is hardware supported, you need to support several different formats and choose the right one at runtime.

# Answer
> 1 votes
To answer your first question, yes it's quite possible to load an ETC2 texture on any OpenGL ES 3.0 device. In fact, it's required by the standard. In order to do so, you replace the `glTexImage2D` function call with `glCompressedTexImage2D`. For more details, read the documentation.

Currently there aren't that many texture compression tools that support ETC2. Off the top of my head I can only think of one. That compressor uses the stock ETC2 compressor that Ericsson released a while back. I believe that the tool can output textures in a KTX file that comes with a codec implementation.

If you want to do compression online in the app, you may be out of luck. A preliminary search on the internet shows that ports of etcpack exist but I've never tried them. In any case you should be able to expect a decent quality compression of a 1024x1024 sized bitmap within 60 seconds of any codec worth it's salt.

# Answer
> 0 votes
I've written a pure java port of ETCPack, including the fast version QuickETC

https://github.com/philjord/ETCPack

This will allow you to compress on line, on the device.

---
Tags: android, textures, opengl-es2, compression
---


# Question
Title: most efficient AABB vs Ray collision algorithms
Is there a known 'most efficient' algorithm for AABB vs Ray collision detection?

I recently stumbled accross Arvo's AABB vs Sphere collision algorithm, and I am wondering if there is a similarly noteworthy algorithm for this.

One must have condition for this algorithm is that I need to have the option of querying the result for the distance from the ray's origin to the point of collision. having said this, if there is another, faster algorithm which does not return distance, then in addition to posting one that does, also posting that algorithm would be very helpful indeed.

Please also state what the function's return argument is, and how you use it to return distance or a 'no-collision' case. For example, does it have an out parameter for the distance as well as a bool return value? or does it simply return a float with the distance, vs a value of -1 for no collision?

(For those that don't know: AABB = Axis Aligned Bounding Box)

# Answer
Andrew Woo, who along with John Amanatides developed the raymarching algorithm (DDA) used ubiquitously in raytracers, wrote "Fast Ray-Box Intersection" (alternative source here) which was published in Graphics Gems, 1990, pp. 395-396. Rather than being built specifically for integration through a grid (eg. a voxel volume) as DDA is (see zacharmarz' answer), this algorithm is specifically suited to worlds that are not evenly subdivided, such as your typical polyhedra world found in most 3D games.

The approach provides support for 3D, and optionally does backface culling. The algorithm is derived from the same principles of integration used in DDAs, so it is *very* quick. More detail can be found in the original Graphics Gems volume (1990).

Many other approaches specifically for Ray-AABB to be found at realtimerendering.com.

EDIT: An alternative, branchless approach -- which would be desirable on both GPU & CPU -- may be found here. The actual code, including the max() on the return test, is available here.
> 33 votes

# Answer
What I have been using earlier in my raytracer:

```
// r.dir is unit direction vector of ray
dirfrac.x = 1.0f / r.dir.x;
dirfrac.y = 1.0f / r.dir.y;
dirfrac.z = 1.0f / r.dir.z;
// lb is the corner of AABB with minimal coordinates - left bottom, rt is maximal corner
// r.org is origin of ray
float t1 = (lb.x - r.org.x)*dirfrac.x;
float t2 = (rt.x - r.org.x)*dirfrac.x;
float t3 = (lb.y - r.org.y)*dirfrac.y;
float t4 = (rt.y - r.org.y)*dirfrac.y;
float t5 = (lb.z - r.org.z)*dirfrac.z;
float t6 = (rt.z - r.org.z)*dirfrac.z;

float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));

// if tmax < 0, ray (line) is intersecting AABB, but the whole AABB is behind us
if (tmax < 0)
{
    t = tmax;
    return false;
}

// if tmin > tmax, ray doesn't intersect AABB
if (tmin > tmax)
{
    t = tmax;
    return false;
}

t = tmin;
return true;

```

If this returns true, it's intersecting, if it returns false, it's not intersecting.

If you use the same ray many times, you can precompute `dirfrac` (only division in whole intersection test). And then it's really fast. And you have also length of ray until intersection (stored in `t`).
> 60 votes

# Answer
Nobody described the algorithm here, but the Graphics Gems algorithm is simply:

1. Using your ray's direction vector, determine which 3 of the 6 candidate planes *would be hit first*. If your (unnormalized) ray direction vector is (-1, 1, -1), then the 3 planes that are possible to be hit are +x, -y, and +z.
2. Of the 3 candidate planes, do find the t-value for the intersection for each. Accept the plane that gets the *largest* **t** value as being the plane that got hit, **and check that the hit is within the box**. The diagram in the text makes this clear:

My implementation:

```
bool AABB::intersects( const Ray& ray )
{
  // EZ cases: if the ray starts inside the box, or ends inside
  // the box, then it definitely hits the box.
  // I'm using this code for ray tracing with an octree,
  // so I needed rays that start and end within an
  // octree node to COUNT as hits.
  // You could modify this test to (ray starts inside and ends outside)
  // to qualify as a hit if you wanted to NOT count totally internal rays
  if( containsIn( ray.startPos ) || containsIn( ray.getEndPoint() ) )
    return true ;

  // the algorithm says, find 3 t's,
  Vector t ;

  // LARGEST t is the only one we need to test if it's on the face.
  for( int i = 0 ; i < 3 ; i++ )
  {
    if( ray.direction.e[i] > 0 ) // CULL BACK FACE
      t.e[i] = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
    else
      t.e[i] = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
  }

  int mi = t.maxIndex() ;
  if( BetweenIn( t.e[mi], 0, ray.length ) )
  {
    Vector pt = ray.at( t.e[mi] ) ;

    // check it's in the box in other 2 dimensions
    int o1 = ( mi + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
    int o2 = ( mi + 2 ) % 3 ;

    return BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) &&
           BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) ;
  }

  return false ; // the ray did not hit the box.
}

```
> 19 votes

# Answer
I'm surprised to see that no one has mentioned the branchless slab method by Tavian

```
bool intersection(box b, ray r) {
    double tx1 = (b.min.x - r.x0.x)*r.n_inv.x;
    double tx2 = (b.max.x - r.x0.x)*r.n_inv.x;

    double tmin = min(tx1, tx2);
    double tmax = max(tx1, tx2);

    double ty1 = (b.min.y - r.x0.y)*r.n_inv.y;
    double ty2 = (b.max.y - r.x0.y)*r.n_inv.y;

    tmin = max(tmin, min(ty1, ty2));
    tmax = min(tmax, max(ty1, ty2));

    return tmax >= tmin;
}

```

Full explanation: https://tavianator.com/fast-branchless-raybounding-box-intersections/
> 15 votes

# Answer
This is my 3D ray / AABox intersection I've been using:

```
bool intersectRayAABox2(const Ray &ray, const Box &box, int& tnear, int& tfar)
{
    Vector3d T_1, T_2; // vectors to hold the T-values for every direction
    double t_near = -DBL_MAX; // maximums defined in float.h
    double t_far = DBL_MAX;

    for (int i = 0; i < 3; i++){ //we test slabs in every direction
        if (ray.direction[i] == 0){ // ray parallel to planes in this direction
            if ((ray.origin[i] < box.min[i]) || (ray.origin[i] > box.max[i])) {
                return false; // parallel AND outside box : no intersection possible
            }
        } else { // ray not parallel to planes in this direction
            T_1[i] = (box.min[i] - ray.origin[i]) / ray.direction[i];
            T_2[i] = (box.max[i] - ray.origin[i]) / ray.direction[i];

            if(T_1[i] > T_2[i]){ // we want T_1 to hold values for intersection with near plane
                swap(T_1,T_2);
            }
            if (T_1[i] > t_near){
                t_near = T_1[i];
            }
            if (T_2[i] < t_far){
                t_far = T_2[i];
            }
            if( (t_near > t_far) || (t_far < 0) ){
                return false;
            }
        }
    }
    tnear = t_near; tfar = t_far; // put return values in place
    return true; // if we made it here, there was an intersection - YAY
}

```
> 4 votes

# Answer
Here is an optimized version of the above which I use for GPU:

```
__device__ float rayBoxIntersect ( float3 rpos, float3 rdir, float3 vmin, float3 vmax )
{
   float t[10];
   t[1] = (vmin.x - rpos.x)/rdir.x;
   t[2] = (vmax.x - rpos.x)/rdir.x;
   t[3] = (vmin.y - rpos.y)/rdir.y;
   t[4] = (vmax.y - rpos.y)/rdir.y;
   t[5] = (vmin.z - rpos.z)/rdir.z;
   t[6] = (vmax.z - rpos.z)/rdir.z;
   t[7] = fmax(fmax(fmin(t[1], t[2]), fmin(t[3], t[4])), fmin(t[5], t[6]));
   t[8] = fmin(fmin(fmax(t[1], t[2]), fmax(t[3], t[4])), fmax(t[5], t[6]));
   t[9] = (t[8] < 0 || t[7] > t[8]) ? NOHIT : t[7];
   return t[9];
}

```
> 4 votes

# Answer
I recently achieved over 61 billion ray/box intersections per second using AVX2 on a Threadripper 3960X (~2 billion single-threaded, ~1.9 cycles per box): https://tavianator.com/2022/ray\_box\_boundary.html. I don't know what the state of the art is exactly, but that seems like more than enough :)

The unvectorized implementation looks like this. It's a simple implementation of the slab method that handles edge cases:

```
void intersections(
    const struct ray *ray,
    size_t nboxes,
    const struct box boxes[nboxes],
    float ts[nboxes])
{
    for (size_t i = 0; i < nboxes; ++i) {
        const struct box *box = &boxes[i];
        float tmin = 0.0, tmax = ts[i];

        for (int j = 0; j < 3; ++j) {
            float t1 = (box->min[j] - ray->origin[j]) * ray->dir_inv[j];
            float t2 = (box->max[j] - ray->origin[j]) * ray->dir_inv[j];

            tmin = min(max(t1, tmin), max(t2, tmin));
            tmax = max(min(t1, tmax), min(t2, tmax));
        }

        ts[i] = tmin <= tmax ? tmin : ts[i];
    }
}

```

The vectorized version is similar, packing 8 boxes per struct: https://tavianator.com/2022/ray\_box\_boundary.html#vectorization
> 2 votes

# Answer
One thing you might want to investigate is rasterizing the front and backfaces of your bounding box in two seperate buffers. Render the x,y,z values as rgb (this works best for a bounding box with one corner at (0,0,0) and the opposite at (1,1,1).

Obviously, this has limited use but I found it great for rendering simple volumes.

For more detail and code:

http://www.daimi.au.dk/~trier/?page\_id=98
> 1 votes

# Answer
Here's the Line vs AABB code I've been using:

```
namespace {
    //Helper function for Line/AABB test.  Tests collision on a single dimension
    //Param:    Start of line, Direction/length of line,
    //          Min value of AABB on plane, Max value of AABB on plane
    //          Enter and Exit "timestamps" of intersection (OUT)
    //Return:   True if there is overlap between Line and AABB, False otherwise
    //Note:     Enter and Exit are used for calculations and are only updated in case of intersection
    bool Line_AABB_1d(float start, float dir, float min, float max, float& enter, float& exit)
    {
        //If the line segment is more of a point, just check if it's within the segment
        if(fabs(dir) < 1.0E-8)
            return (start >= min && start <= max);

        //Find if the lines overlap
        float   ooDir = 1.0f / dir;
        float   t0 = (min - start) * ooDir;
        float   t1 = (max - start) * ooDir;

        //Make sure t0 is the "first" of the intersections
        if(t0 > t1)
            Math::Swap(t0, t1);

        //Check if intervals are disjoint
        if(t0 > exit || t1 < enter)
            return false;

        //Reduce interval based on intersection
        if(t0 > enter)
            enter = t0;
        if(t1 < exit)
            exit = t1;

        return true;
    }
}

//Check collision between a line segment and an AABB
//Param:    Start point of line segement, End point of line segment,
//          One corner of AABB, opposite corner of AABB,
//          Location where line hits the AABB (OUT)
//Return:   True if a collision occurs, False otherwise
//Note:     If no collision occurs, OUT param is not reassigned and is not considered useable
bool CollisionDetection::Line_AABB(const Vector3D& s, const Vector3D& e, const Vector3D& min, const Vector3D& max, Vector3D& hitPoint)
{
    float       enter = 0.0f;
    float       exit = 1.0f;
    Vector3D    dir = e - s;

    //Check each dimension of Line/AABB for intersection
    if(!Line_AABB_1d(s.x, dir.x, min.x, max.x, enter, exit))
        return false;
    if(!Line_AABB_1d(s.y, dir.y, min.y, max.y, enter, exit))
        return false;
    if(!Line_AABB_1d(s.z, dir.z, min.z, max.z, enter, exit))
        return false;

    //If there is intersection on all dimensions, report that point
    hitPoint = s + dir * enter;
    return true;
}

```
> 1 votes

# Answer
This seems similar to the code posted by zacharmarz.
I got this code from the book 'Real-Time Collision Detection' by Christer Ericson under the section '5.3.3 Intersecting Ray or Segment Against Box'

```
// Where your AABB is defined by left, right, top, bottom

// The direction of the ray
var dx:Number = point2.x - point1.x;
var dy:Number = point2.y - point1.y;

var min:Number = 0;
var max:Number = 1;

var t0:Number;
var t1:Number;

// Left and right sides.
// - If the line is parallel to the y axis.
if(dx == 0){
    if(point1.x < left || point1.x > right) return false;
}
// - Make sure t0 holds the smaller value by checking the direction of the line.
else{
    if(dx > 0){
        t0 = (left - point1.x)/dx;
        t1 = (right - point1.x)/dx;
    }
    else{
        t1 = (left - point1.x)/dx;
        t0 = (right - point1.x)/dx;
    }

    if(t0 > min) min = t0;
    if(t1 < max) max = t1;
    if(min > max || max < 0) return false;
}

// The top and bottom side.
// - If the line is parallel to the x axis.
if(dy == 0){
    if(point1.y < top || point1.y > bottom) return false;
}
// - Make sure t0 holds the smaller value by checking the direction of the line.
else{
    if(dy > 0){
        t0 = (top - point1.y)/dy;
        t1 = (bottom - point1.y)/dy;
    }
    else{
        t1 = (top - point1.y)/dy;
        t0 = (bottom - point1.y)/dy;
    }

    if(t0 > min) min = t0;
    if(t1 < max) max = t1;
    if(min > max || max < 0) return false;
}

// The point of intersection
ix = point1.x + dx * min;
iy = point1.y + dy * min;
return true;

```
> 0 votes

# Answer
I have added to @zacharmarz answer to handle when the ray origin is inside of the AABB. In this case tmin will be negative and behind the ray so tmax is the first intersection between the ray and AABB.

```
// r.dir is unit direction vector of ray
dirfrac.x = 1.0f / r.dir.x;
dirfrac.y = 1.0f / r.dir.y;
dirfrac.z = 1.0f / r.dir.z;
// lb is the corner of AABB with minimal coordinates - left bottom, rt is maximal corner
// r.org is origin of ray
float t1 = (lb.x - r.org.x)*dirfrac.x;
float t2 = (rt.x - r.org.x)*dirfrac.x;
float t3 = (lb.y - r.org.y)*dirfrac.y;
float t4 = (rt.y - r.org.y)*dirfrac.y;
float t5 = (lb.z - r.org.z)*dirfrac.z;
float t6 = (rt.z - r.org.z)*dirfrac.z;

float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));

// if tmax < 0, ray (line) is intersecting AABB, but the whole AABB is behind us
if (tmax < 0)
{
    t = tmax;
    return false;
}

// if tmin > tmax, ray doesn't intersect AABB
if (tmin > tmax)
{
    t = tmax;
    return false;
}

// if tmin < 0 then the ray origin is inside of the AABB and tmin is behind the start of the ray so tmax is the first intersection
if(tmin < 0) {
  t = tmax;
} else {
  t = tmin;
}
return true;

```
> 0 votes

# Answer
## C++ Code

Here is a quasi-branchless and very robust version written in C++:

```
ray_intersection intersect(vec3 origin, vec3 direction, vec3 box_min, vec3 box_max) {
    vec3 t0 = (box_min - origin) / direction;
    vec3 t1 = (box_max - origin) / direction;
    vec3 min = ray_box_min(t0, t1); // entry points per plane
    vec3 max = ray_box_max(t0, t1); // exit points per plane
    double t_min = std::fmax(std::fmax(min.x, min.y), min.z);
    double t_max = std::fmin(std::fmin(max.x, max.y), max.z);
    return { t_min, t_max };
}

```

This also requires the use of two utility functions:

```
double ray_box_min(double x, double y) {
    return std::isnan(x) || std::isnan(y) ? -inf : std::fmin(x, y);
}

double ray_box_max(double x, double y) {
    return std::isnan(x) || std::isnan(y) ? +inf : std::fmax(x, y);
}

vec3 ray_box_min(vec3 a, vec3 b) {
    return { ray_box_min(a.x, b.x), ray_box_min(a.y, b.y), ray_box_min(a.z, b.z) };
}

vec3 ray_box_max(vec3 a, vec3 b) {
    return { ray_box_max(a.x, b.x), ray_box_max(a.y, b.y), ray_box_max(a.z, b.z) };
}

```

## Explanation

This implements the well-known Slab method.

All operations including `/` and `min`/`max` are component-wise when applied to vectors in this code.

We cannot use regular `std::fmin` but must use a custom `ray_box_min` for numerical stability. If the ray origin is inside a box plane and the ray direction is parallel to the box plane, the first division yields NaN. We replace this with `-inf` and `+inf` depending on the operation. This results in the value getting replaced by others when computing `t_min` or `t_max`.

If you can guarantee that the ray origin is outside the box, you can use a regular component-wise `min` and `max` instead of the `ray_box_` variants.

### Interpreting the results

* `t_min` is the furthest entry point
* `t_max` is the closest exit point

From these values, we can obtain all sorts of properties:

* If `t_min <= t_max`, the intersection is not a miss.
    + If also `t_min > 0`, the intersection is completely in front.
    + If also `t_max < 1`, the intersection is completely behind.
        - If also `t_min < 0 && t_max > 0`, the ray origin is inside the box.
* If `t_min` is NaN or `t_max` is NaN, the ray direction is the zero-vector.
* If `t_min == 0`, the ray origin lies on the box surface.
* If `t_min == t_max`, the box has no volume, or an edge or corner was hit. Either way, the intersection is a single point, not a line segment.
> 0 votes

---
Tags: collision-detection, aabb
---


# Question
Title: How to add a text label to a WireSphere Gizmo?
I’ve created a few WireSphere gizmos on my scene, and I’d like to add labels to them so I can easily identify which corresponds to what variable. However, by using **transform.position**, the label appears at the center (or pivot?) of the Game Object that has the gizmo. I’d like to display the label right at the edge of the WireSphere, but when I tried doing **transform.position * \_radius**, the label appears many meters away from the gizmo. It seems that this could be solved with an offset value, but it has to be very high for it to work (like 20+).

Is there a better way to achieve this?

# Answer
> 1 votes
Did you mean `transform.position + Vector3.up * _radius`?

You want to scale the offset, not scale the position. Otherwise an object at 0,0,0 gets no offset and an object at 1000,1000,1000 has its label flung thousands of units away.

---
Tags: unity, editors
---


# Question
Title: How do I restore the cooldown time left I have previously stored?
Wether I convert the timer's `.time_left` to an interger or a float it always gives me an error saying

`"Invalid set index 'time_left' (on base: 'Timer') with value of type 'float'."`

or

`"Invalid set index 'time_left' (on base: 'Timer') with value of type 'int'."`

here's the code:

```
if "unstuck_cooldown" in player_data:
    $Minimap/Unstcuk/UnstuckCDTimer.time_left = int(player_data["unstuck_cooldown"])

```

# Answer
The property `time_left` is read only.

If your time is not repeating, then it would be sufficient to create a new timer for the save `time_left` by setting its `wait_time` or passing the saved `time_left` to the `start` method. However, if you timer must repeat, that won't work correctly. So you would have to change `wait_time` on the first `timeout`.
> 2 votes

---
Tags: godot, savegame
---


# Question
Title: Is there a way to instantiate a custom class decided at runtime in GDScript?
Can I instantiate a custom class during runtime through a String without knowing the value of the string when writing the code? Example:

```
var className: String
#Code...
#An unknown value will be assigned to the variable className
Instantiate(className)
#Is there a way to instantiate the class name contained in the value of the variable className?

```

# Answer
If it is a built-in class, you can use `ClassDB.instantiate(name_of_class)`.

---

If you need to pick from a list of scripts, you can create a dictionary, for example:

```
static var script_map := {
    "Character": Character,
    "OtherClass": OtherClass
}

static func instantiate_class(name_of_class:String) -> Object:
    if script_map.has(name_of_class):
        var script := script_map[name_of_class] as GDScript
        if script != null:
            return script.new()

    return null

```

---

If you need to instantiate any class... Well, first let us figure out if it is a built-in class or not. If it is, we can instantiate it with `ClassDB`. Otherwise we need to get the `Script` from the name...

```
static func instantiate_class(name_of_class:String) -> Object:
    if name_of_class.is_empty():
        return null

    var result:Object = null
    if ClassDB.class_exists(name_of_class):
        result = ClassDB.instantiate(name_of_class)
    else:
        var script := get_script_by_name(name_of_class)
        if script is GDScript:
            result = (script as GDScript).new()
        else:
            return null

    return result

```

To get the script from the name, I'll start by trying to load it, which allows to pass a resource path ("res://..."), otherwise we search for it in project settings:

```
static func get_script_by_name(name_of_class:String) -> Script:
    if ResourceLoader.exists(name_of_class, "Script"):
        return load(name_of_class) as Script

    for global_class in ProjectSettings.get_global_class_list():
        var found_name_of_class:String = global_class["class"]
        var found_path:String = global_class["path"]
        if found_name_of_class == name_of_class:
            return load(found_path) as Script

    return null

```

Some optimizations are possible (e.g. loading the list of classes to a `Dictionary` \- perhaps lazily - so we do not need to iterate over the list multiple times).

---

**Notes**:

* As you know you can reference a class by name. If you need a class that does not have a name, you can use `preload` instead, which is a constant expression (so you can store it in a constant which you use as if it were the class name).
* If the class `_init` has parameters, you would have to pass them in `new`, so the code above would fail.
* The code above only supports `GDScript` classes and built-in classes. When you load a `Script`, you need to cast to the correct subclass to be able to call `new` on it, so if you need to support other languages you need to extend this code.
* GDScript nested classes are not `Script`s, and casting them to `Script` was a bug.
> 3 votes

---
Tags: godot, gdscript, godot-4
---


# Question
Title: What data structure would be the most efficient for a task scheduler?
So in a game with various objects that perform various tasks, a naive approach would simply be to update the state of *all* of the existing items in the world every game update. This is what Minecraft does to handle furnaces, and similar items. A more efficient approach would be to schedule a task in the future, for example, when the next item will be smelted. Then only the current events need to be processed rather than all of them every update.

An implementation of this would be to have a sorted list, and every update, the start of the list is iterated and the items processed until a list item is reached that is scheduled to occur in a future update.

But what data structure would be most suitable?

* If I use a straight array, then only one allocation is used, but every time an element is inserted or removed, that will incur a shift of the remaining elements. `O(n)` complexity. The correct insertion point for an event scheduled to occur at an arbitrary time could be found via binary search with `O(log n)` complexity.
* If I use a linked list, then deleting the first few elements scheduled to occur in the current update would not entail traversing the entire list. But scheduling a new event would entail doing so, in order to find the correct insertion point.

What data structure would be most suitable for a constantly changing, ordered set like a scheduled events list? So far my only options have linear complexity for insertion and/or deletion. Is there an even better data structure that will have logarithmic or constant time complexity for that?

# Answer
Two options you could consider:

* Ring buffer \- this just an array with an index to the first/last element, wrapping around from the end of the array to the start using modular arithmetic. When you want to extract the first element, you increment the "first" index instead of shifting all the items down, making it O(1) to extract. It's is still O(n) to insert, though for this use case it sounds like you'd typically be inserting closer to the end than the start, since a newly scheduled task will often take as long to finish as anything that was scheduled earlier. This is especially true if you use multiple queues, one for short tasks and one for long tasks, so you don't have lots of short tasks jumping in line in front of long tasks and forcing them to move down.
* Min Heap \- this is a binary tree where each child's key (completion time) is greater than or equal to its parent's. That makes it O(log n) both to insert an entry or extract the entry with the minimum key (earliest completion time)

Myself, I'd start with the ring buffer, since it's simpler code with less branching and more linear memory access, making it more cache-friendly. I'd expect that to outpace the heap up to values of n in the thousands, especially if your task durations are large relative to the time between additions to the queue (minimizing shifting work).
> 1 votes

# Answer
My recommendation would be to start with the simplest possible data structure, and hide it behind an interface that lets you replace the implementation later if you run into problems. Focus on what operations you need to do, and only implement those that you need.

Having said that, a Priority Queue sounds like it should serve your needs - it lets you add things in any order, and efficiently retrieve them in sorted order.
> 0 votes

---
Tags: data-structure
---


# Question
Title: Is it possible to prepare a generic bump map shader to be used by (injected at) any 3D game?
Is it possible to prepare a generic bump map shader to be used by any 3D game?

I found this bump map shader:

```
Shader "Custom/BumpedEnvironment" {
   Properties {
      _myDiffuse ("Diffuse Texture", 2D) = "white" {}
      _myBump ("Bump Texture", 2D) = "bump" {}
      _mySlider ("Bump Amount", Range(0,10)) = 1
      _myBright ("Brightness", Range(0,10)) = 1
      _myCube ("Cube Map", CUBE) = "white" {}
   }
   SubShader {

      CGPROGRAM

      #pragma surface surf Lambert

        sampler2D _myDiffuse;
        sampler2D _myBump;
        half _mySlider;
        half _myBright;
        samplerCUBE _myCube;

      struct Input {
         float2 uv_myDiffuse;
         float2 uv_myBump;
         float3 worldRefl; INTERNAL_DATA  // <- THIS IS VERY IMPORTANT
      };

      void surf (Input IN, inout SurfaceOutput o) {
          o.Albedo = tex2D(_myDiffuse, IN.uv_myDiffuse).rgb;
          o.Normal = UnpackNormal(tex2D(_myBump, IN.uv_myBump)) * _myBright;
          o.Normal *= float3(_mySlider, _mySlider, 1);
          o.Emission = texCUBE(_myCube, WorldReflectionVector(IN, o.Normal)).rgb;

      }

      ENDCG
   }
   FallBack "Diffuse"
}

```

I want to let Arx Libertatis use that shader, but I would like also to let other 3D games that do not have it, to be able to use it too (see OpenSourcedGames.

Is the only way to adapt that shader inside the game engine, so the game engine itself send it to the GPU?

Or is it possible to compile a generic bump map shader like the above, load it into the GPU (while or before the game start to run) and force the GPU to apply that shader to specific 3D games? It would be like injecting a shader into a game I guess.

If it is possible, any tips how should I start doing it? the easiest way if possible, as I am very new to shaders.

I am not restricting the answer to Linux. If the answer can also work on Linux, it would be better though.

I just found about ENB, but it doesn't work on Linux. There is this that could work on Linux (there is a Linux instruction folder inside it; any newer version may have it too) but it requires Wine, and therefore a Windows compiled game binary, and I develop projects on Linux, compiled for Linux.
So, What I mean is, unless there is some equivalent to ENB that works on Linux (may be Mac) too, my main request/question is how can I do it myself instead of using some ready tool.

# Answer
> 2 votes
No, you won't be able to make a normal mapping shader that can be *universally* applied to *any* game that doesn't already use one. Even assuming you have a perfect injection system that can add your custom shader to specific draw calls, there are two main obstacles:

1. **Tangent space normal mapping requires the shader to receive tangent vector information**, used to orient the bumps the right way along the object's surfaces. If the game was not already using normal mapping, it likely will not include this information in the vertex data it sends to the GPU. I have seen shaders try to approximate tangent space using screen space derivatives, but I suspect that would show artifacts.

You could use object space normal mapping instead, but this would require you to create an object space normal map for each object in each game you want this to apply to. It would show artifacts for any objects that don't have a fully unique unwrap (i.e. the same part of the texture is used for multiple parts of the object).

The bigger obstacle though is...
2. For normal maps to apply shading to their bumps correctly, they need access to information about where the light is shining from or what colour it is. **There is no standard way to convey this information to the GPU**. Every game can implement lights in its own quirky way.

You would need to write a custom version of this shader for every rendering engine, and possibly many variants for some rendering engines that switch between different versions of lighting shaders depending on the lighting conditions (e.g. spot vs directional vs point vs cube map vs spherical harmonics, distance/level of detail trade-offs, shadowing...).

You can still probably make a shader you can inject into a single game of interest, and it may even work on other games by the same studio/using the same engine. But making one that works with "*any* 3D game" is definitely off the table.

---
Tags: shaders
---


# Question
Title: Simulating the behaviour of small objects coming to rest on the surface of an asteroid, 2D
I have a large asteroid object, and I want to use physics2D to have smaller objects be attracted to it as if by gravity, and come to rest on its surface. The asteroid itself is also a dynamic physics2D object to allow it to drift around, and receive transferred momentum from impacts.

My current arrangement on the asteroid object is:

* Smaller CircleCollider2D on surface of asteroid asset for collisions
* RigidBody2D
* Larger CircleCollider2D for point effector
* PointEffector2D with negative force to attract objects

Other objects are just colliders and rigidBody2D's

The problem is that when an object comes to rest on the surface of the asteroid, since it has not reached the actual point effector coordinates, a force is still applied to that object in the direction of the point effector ie center of the asteroid. This force in turn gets imparted on to the asteroid, and if several objects build up in a certain direction the asteroid will move in the opposite direction.

How can I approximate the behavior of a real asteroid whereby an object will impart some momentum on impact, but once they come to rest the forces reach equilibrium?

Obviously in real life the center of gravity would be slightly altered, I don't need that level of precision. I just don't want the asteroid zipping around.

I have tried using the collision masks / matrix. I can not find a configuration that both allows the asteroid to collide with the smaller objects, but not receive the force imparted by them after colliding.

# Answer
> 1 votes
This solution worked for me:

```
private Vector2 totalForce;

private void FixedUpdate()
{
    _rigidBody.AddForce(-totalForce);
    totalForce = Vector2.zero;

    foreach (var rb in affectedRigidbodies)
    {
        Vector3 forceDirection = ((Vector2)transform.position - rb.position).normalized;
        float forceMagnitude = _timeNumberMgmt.hourGravForceMag * rb.mass;
        Vector2 force = forceDirection * forceMagnitude;
        rb.AddForce(force);
        totalForce += force;
    }
}

private void OnTriggerEnter2D(Collider2D other)
{
    Rigidbody2D rb = other.GetComponent<Rigidbody2D>();
    if (rb != null)
    {
        affectedRigidbodies.Add(rb);
    }
}

void OnTriggerExit2D(Collider2D other)
{
    Rigidbody2D rb = other.GetComponent<Rigidbody2D>();
    if (rb != null)
    {
        affectedRigidbodies.Remove(rb);
    }
}

```

A point effector based system seemed more performant. However using `RigidBody.AddForce()` more closely resembles Newtonian gravity as all objects accelerate at the same speed towards the attractor irrespective of their mass, whereas a point effector has a more gradual effect on objects of greater mass.

It also allows me to accumulate the total force of the system and apply the inverse of that to the attractor, which neutralizes the net pushing force the objects are imparting on the attractor while still simulating transfer of momentum from large impacts.

It deliberately ignores the inverse square scaling of newtonian gravity as that isn't desired for my purposes, but that would be easy enough to implement.

I expect there is a more efficient way but this works for now.

---
Tags: unity, physics
---


# Question
Title: How is rotation defined in a tetris game?
I'm working on implementing the backend logic behind the classical tetris game, and I'm a bit confused on how a rotation is performed. I understand that you can apply a rotation matrix, but I still have some questions that are perhaps better explained with an example.

In my implementation, I use square matrices of 0s and 1s to represent the shape. e.g., I use a 4x4 matrix with a single row filled to represent the long horizontal block: $$ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

And for each block, I also keep track of the bottom right location of the 4x4 matrix relative to the location of the game board.

The question I have is, when you apply a rotation (in this case it would turn into a vertical block), do you have to fix some center? If so, how is this center of rotation defined?

e.g., I could define the center of rotation of the above as the top left element, so apply 90 degree clockwise rotation would yield:

$$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} $$

But you could also make any of the other 15 elements the center of rotation, though it probably makes the most sense to make one of the 4 elements of the original block the center of rotation. I think the issue here is that for the other 3 elements, if you make any of them the center of rotation, part of the rotated block is going to lie outside the existing 4x4 window. So how is something like this prescribed in an implementation?

Alternatively you can swap the indices as in Tetris - Rotations using Linear Algebra (Rotation Matrices) without using a center of rotation, but I'm not sure which approach makes the most sense. Swapping indices is certainly much easier to implement.

# Answer
> 17 votes
It works however you (as he game designer) define it. Various implementations of Tetris have implemented rotations in different ways:

Super Rotation System is the current Tetris Guideline standard for how tetrominoes behave, defining where and how the tetrominoes spawn, how they rotate, and what wall kicks they may perform. Henk Rogers developed this system in order to unify all new Tetris games under the Tetris Guideline:

* When unobstructed, the tetrominoes all appear to rotate purely about a single point & is solely a mathematical rotation as opposed to the combination of rotation and translation found in some other systems.

The NES and SNES use a "right handed rotation system":

* O : no rotations.
* I : two rotations, favoring the lower half when horizontal, and the right half when vertical.
* J, L, and T : 4 rotations centered around the middle square of the three square edge.
* S and Z : four rotations, favoring the bottom and right sides.

The Game Boy Tetris is identical to the NES version it uses a left hand rotation for the S and Z pieces.

Sega rotation system is similar to the NES version, except that:

* The flat-side-down states of J, L, and T are pushed down by one space
* S and Z round in different directions
* I rounds differently from the other pieces.
* I requires more space under it to rotate to a vertical orientation.

The above mostly covers the 'basic' rotations - the various systems have varying rules for things like wall kicks and spawning orientations. More information can be found here.

Subjectively, I wouldn't expect the I rotation to behave as you've described in your question because it differs strongly from the precedents I'm familiar with, but that doesn't necessarily make it wrong. Test it out and focus on *how it plays* rather than *how it's implemented*. If it play tests well and meets your design goals, then it is a working design.

---
Tags: tetris
---


# Question
Title: Is wireframe effect possible without geometry shader?
I am trying to write a shader that highlight the edge between each pair of vertices, much like the *UCLA Wireframe Shader*.

All implementations I came across require geometry shader support. I am wondering if this is possible with just vertex and fragment shaders?

(Of course, I can use texture to workaround it; but I am trying to avoid create custom textures for each model that I need this effect. On the other hand, I could just use geometry shader but it presents quite a problem when porting to iOS, which lacks support.)

# Answer
Yes, there are several great wireframe shaders that you can use, for free:

https://forum.unity.com/threads/is-wireframe-effect-possible-without-geometry-shader.442625/#post-9546460

Here is the best one from it (by Unity), in my opinion. It's called SpatialMappingWireframe and I modified it to include texture and to have constant color. I also made it work with single (non-stereo camera)

```
// Unity built-in shader source. Copyright (c) 2016 Unity Technologies. MIT license (see license.txt)
// from https://github.com/TwoTailsGames/Unity-Built-in-Shaders/blob/master/DefaultResourcesExtra/VR/Shaders/SpatialMappingWireframe.shader
// This is adjusted version, allowing to tweak color of Wireframe, make it barely visible (alpha of color).
// Allows for a texture.
Shader "Custom/VRWireframe (Unlit Texture)"
{
    Properties
    {
        _WireThickness ("Wire Thickness", RANGE(0, 800)) = 100
        _MainTex("MainTexture", 2D) = "white"{}
        _WireColor("Wireframe Color", Color) = (1,1,1,1)
    }

    SubShader
    {
        Tags { "RenderType"="Opaque" }

        Pass
        {
            // Wireframe shader based on the the following
            // http://developer.download.nvidia.com/SDK/10/direct3d/Source/SolidWireframe/Doc/SolidWireframe.pdf

            CGPROGRAM
            #pragma vertex vert
            #pragma geometry geom
            #pragma fragment frag

            #include "UnityCG.cginc"

            float _WireThickness;
            sampler2D _MainTex;
            fixed4 _WireColor;

            struct appdata
            {
                float4 vertex : POSITION;
                float2 uv : TEXCOORD0;
            };

            struct v2g
            {
                float4 projectionSpaceVertex : SV_POSITION;
                float2 uv : TEXCOORD0;
                float4 worldSpacePosition : TEXCOORD1;
            };

            struct g2f
            {
                float4 projectionSpaceVertex : SV_POSITION;
                float2 uv : TEXCOORD0;
                float4 worldSpacePosition : TEXCOORD1;
                float4 dist : TEXCOORD2;
            };

            v2g vert (appdata v)
            {
                v2g o;
                o.projectionSpaceVertex = UnityObjectToClipPos(v.vertex);
                o.worldSpacePosition = mul(unity_ObjectToWorld, v.vertex);
                o.uv = v.uv;
                return o;
            }

            [maxvertexcount(3)]
            void geom(triangle v2g i[3], inout TriangleStream<g2f> triangleStream)
            {
                float2 p0 = i[0].projectionSpaceVertex.xy / i[0].projectionSpaceVertex.w;
                float2 p1 = i[1].projectionSpaceVertex.xy / i[1].projectionSpaceVertex.w;
                float2 p2 = i[2].projectionSpaceVertex.xy / i[2].projectionSpaceVertex.w;

                float2 edge0 = p2 - p1;
                float2 edge1 = p2 - p0;
                float2 edge2 = p1 - p0;

                // To find the distance to the opposite edge, we take the
                // formula for finding the area of a triangle Area = Base/2 * Height,
                // and solve for the Height = (Area * 2)/Base.
                // We can get the area of a triangle by taking its cross product
                // divided by 2.  However we can avoid dividing our area/base by 2
                // since our cross product will already be double our area.
                float area = abs(edge1.x * edge2.y - edge1.y * edge2.x);
                float wireThickness = 800 - _WireThickness;

                g2f o;
                o.worldSpacePosition = i[0].worldSpacePosition;
                o.projectionSpaceVertex = i[0].projectionSpaceVertex;
                o.dist.xyz = float3( (area / length(edge0)), 0.0, 0.0) * o.projectionSpaceVertex.w * wireThickness;
                o.dist.w = 1.0 / o.projectionSpaceVertex.w;
                o.uv = i[0].uv;
                triangleStream.Append(o);

                o.worldSpacePosition = i[1].worldSpacePosition;
                o.projectionSpaceVertex = i[1].projectionSpaceVertex;
                o.dist.xyz = float3(0.0, (area / length(edge1)), 0.0) * o.projectionSpaceVertex.w * wireThickness;
                o.dist.w = 1.0 / o.projectionSpaceVertex.w;
                o.uv = i[1].uv;
                triangleStream.Append(o);

                o.worldSpacePosition = i[2].worldSpacePosition;
                o.projectionSpaceVertex = i[2].projectionSpaceVertex;
                o.dist.xyz = float3(0.0, 0.0, (area / length(edge2))) * o.projectionSpaceVertex.w * wireThickness;
                o.dist.w = 1.0 / o.projectionSpaceVertex.w;
                o.uv = i[2].uv;
                triangleStream.Append(o);
            }

            fixed4 frag (g2f i) : SV_Target{
                float minDistanceToEdge = min(i.dist[0], min(i.dist[1], i.dist[2])) * i.dist[3];

                // Early out if we know we are not on a line segment.
                float4 texCol = tex2D(_MainTex, i.uv);

                // Smooth our line out
                float t = exp2(-2 * minDistanceToEdge * minDistanceToEdge);
                      t *= _WireColor.a;

                fixed4 finalColor = lerp(texCol, _WireColor, t);
                finalColor.a = 1;

                return finalColor;
            }
            ENDCG
        }
    }
}

```
> 2 votes

# Answer
Have you considered https://docs.unity3d.com/ScriptReference/GL-wireframe.html ?

Alternatively, you could generate the lines by yourself and add them to a mesh with a line topology.
> 1 votes

---
Tags: unity, shaders
---


# Question
Title: Increasing efficiency of N-Body gravity simulation
I'm making a space exploration type game, it will have many planets and other objects that will all have realistic gravity. I currently have a system in place that works, but if the number of planets goes above 70, the FPS decreases an practically exponential rates. I'm making it in C# and XNA.

My guess is that I should be able to do gravity calculations between 100 objects without this kind of strain, so clearly my method is not as efficient as it should be.

I have two files, Gravity.cs and EntityEngine.cs. Gravity manages JUST the gravity calculations, EntityEngine creates an instance of Gravity and runs it, along with other entity related methods.

**EntityEngine.cs**

```
        public void Update()
        {
            foreach (KeyValuePair<string, Entity> e in Entities)
            {
                e.Value.Update();
            }

            gravity.Update();
        }

```

(Only relevant piece of code from EntityEngine, self explanatory. When an instance of Gravity is made in entityEngine, it passes itself (this) into it, so that gravity can have access to entityEngine.Entities (a dictionary of all planet objects))

**Gravity.cs**

```
namespace ExplorationEngine
{
    public class Gravity
    {
        private EntityEngine entityEngine;
        private Vector2 Force;
        private Vector2 VecForce;
        private float distance;
        private float mult;

        public Gravity(EntityEngine e)
        {
            entityEngine = e;
        }

        public void Update()
        {
            //First loop
            foreach (KeyValuePair<string, Entity> e in entityEngine.Entities)
            {
            //Reset the force vector
            Force = new Vector2();

                //Second loop
                foreach (KeyValuePair<string, Entity> e2 in entityEngine.Entities)
                {
                    //Make sure the second value is not the current value from the first loop
                    if (e2.Value != e.Value )
                    {
                        //Find the distance between the two objects. Because Fg = G * ((M1 * M2) / r^2), using Vector2.Distance() and then squaring it
                        //is pointless and inefficient because distance uses a sqrt, squaring the result simple cancels that sqrt.
                        distance = Vector2.DistanceSquared(e2.Value.Position, e.Value.Position);

                        //This makes sure that two planets do not attract eachother if they are touching, completely unnecessary when I add collision,
                        //For now it just makes it so that the planets are not glitchy, performance is not significantly improved by removing this IF
                        if (Math.Sqrt(distance) > (e.Value.Texture.Width / 2 + e2.Value.Texture.Width / 2))
                        {
                            //Calculate the magnitude of Fg (I'm using my own gravitational constant (G) for the sake of time (I know it's 1 at the moment, but I've been changing it)
                            mult = 1.0f * ((e.Value.Mass * e2.Value.Mass) / distance);

                            //Calculate the direction of the force, simply subtracting the positions and normalizing works, this fixes diagonal vectors
                            //from having a larger value, and basically makes VecForce a direction.
                            VecForce = e2.Value.Position - e.Value.Position;
                            VecForce.Normalize();

                            //Add the vector for each planet in the second loop to a force var.
                            Force = Vector2.Add(Force, VecForce * mult);
                            //I have tried Force += VecForce * mult, and have not noticed much of an increase in speed.
                        }
                    }
                }

                //Add that force to the first loop's planet's position (later on I'll instead add to acceleration, to account for inertia)
                e.Value.Position += Force;
            }

        }

    }
}

```

I have used various tips (about gravity optimizing, not threading) from THIS question (that I made yesterday). I've made this gravity method (Gravity.Update) as efficient as I know how to make it. This O(N^2) algorithm still seems to be eating up all of my CPU power though.

Here is a LINK (google drive, go to File \> download, keep .Exe with the content folder, you will need XNA Framework 4.0 Redist. if you don't already have it) to the current version of my game. Left click makes a planet, right click removes the last planet. Mouse moves the camera, scroll wheel zooms in and out. Watch the FPS and Planet Count to see what I mean about performance issues past 70 planets. (ALL 70 planets must be moving, I've had 100 stationary planets and only 5 or so moving ones while still having 300 fps, the issue arises when 70+ are moving around)

After 70 planets are made, performance tanks exponentially. With \< 70 planets, I get 330 fps (I have it capped at 300). At 90 planets, the FPS is about 2, more than that and it sticks around at 0 FPS. Strangely enough, when all planets are stationary, the FPS climbs back up to around 300, but as soon as something moves, it goes right back down to what it was, I have no systems in place to make this happen, it just does.

I considered multithreading, but that previous question I asked taught me a thing or two, and I see now that that's not a viable option.

I've also thought maybe I could do the calculations on my GPU instead, though I don't think it should be necessary. I also do not know how to do this, it is not a simple concept and I want to avoid it unless someone knows a really noob friendly simple way to do it that will work for an n-body gravity calculation. (I have an NVidia gtx 660)

Lastly I've considered using a quadtree type system. (Barnes Hut simulation) I've been told (in the previous question) that this is a good method that is commonly used, and it seems logical and straightforward, however the implementation is way over my head and I haven't found a good tutorial for C# yet that explains it in a way I can understand, or uses code I can eventually figure out.

So my question is this: How can I make my gravity method more efficient, allowing me to use more than 100 objects (I can render 1000 planets with constant 300+ FPS without gravity calculations), and if I can't do much to improve performance (including some kind of quadtree system), could I use my GPU to do the calculations?

# Answer
Your approach and implementation are valid (disregarding that `position += force` line). As long as there is only one instance of `gravity`. There is nothing in the code you have provided that leads to an over-O(n²) runtime. Therefore it is reasonable to expect a drop in framerate by half at 100 planets. That is 100 planets at 150fps. 200 planets at 30fps. etc.

As this does not match with your observations some questions arise. Most prominently: Are you sure the fps are lost in `gravity.Update`? Have you **measured it with a profiler**? Which statement is the offender? Is there any notable difference in memory consumption? Is the garbage collector busy? Can you render 100-200 planets at 300fps when there is no gravity?
> 6 votes

# Answer
You could easily double your speed by adding the gravity force calculated to BOTH objects involved.

You are calculating the force between A & B and the later calculating the force between B & A, but of course, it's the same force in both cases. No need to calculate it twice.

To do this you will need to restructure your loops so that you are calculating the gravity between e1 and only the objects AFTER e1 in your entity list.

```
//pseudo code
for(i=0 to num_objects){
    for(j=i+1 to num_objects){ //inner loop starts just after position in outer loop
        f=calc_force_between_objects(i,j)
        i.forces+=f;
        j.forces+=-f; // same force, opposite direction
    }
}

```
> 5 votes

# Answer
If your universe is divided up in to natural clusters (e.g. a number of solar-systems) Then you can treat each cluster as a single gravitational body for the purposes of gravity simulation (just sum the masses of the objects in the cluster and do a weighted(!) average their positions to get the centre of mass of the cluster). If the cluster is dominated by a large body, e.g. a sun, the just use that as the centre of mass.

This will work fairly accurately for bodies not close the the cluster.

You may also have clusters within clusters. e.g Jupiter and it's moons, is a cluster within the solar system.
> 3 votes

# Answer
Ok I am going to give you simplified answer here. Start with creating a spatial structure like a quadtree. There are plenty of C# docs about this online.

The main idea is to divide your galaxy into a grid, you start with one big cell and divide it into 4 evenly sized cells and so on. Here is an article about QT in C#, but please try to unerstand the concept and don´t copy - paste, as your problem calls for a very special implementation.

After reading the article you should be aware of a mechanism that lets particles register with cells if they move. So if particle A moves from cell \[1,1\] to cell \[2,1\], then it has to unregister itself in the first cell and register itself in the second cell.

With this structure you gain a tree, with different granularity. What you can now do is creating a Level of Detail for your mass points. On the finest level (the leafs of the tree) each particle will have its own mass and center. If you now step one level up, you will have a node which contains a number of leafs (planets). You now calculate the center of mass and the mass for all planets combined (by c\*alculating the median position of all planets\* and *adding the mass up*).

Now you again step a level up and got a node containing a number of sub nodes (which we just calculated). Now you do the same thing again and generate a new center of mass and a new added mass. Continue with this process until you reach the root node. You will now have a tree, where all planets are singel leafs and every node contains the median center and cummulated mass of all planets below it.

In your Update-logic you now won´t check against every single planet any more. You will *calculate the exact force for planets close to the object* (maybe the same node level). For *planets further away* you will not step down into the tree until you reach leafs, instead you will use the previously calculated median values to *genereate and approximated force*.

Whenever a *planet / object changes its tree-cell* you need to *recalculate the tree from there upwards*, but it should still reduce your calculations by a great amound.

Try to implement a system like this and play with the paramters. You should be able to create a quite powerfull system with this tools.

This is a lot of text, try to wrap your head around this and feel free to comment back for questions :)

PS: Its baffeling me that your movings planets create such a huge drop, as you are calculating gravity for static ones too (aren´t you?) maybe there is a also a problem in the movement code.

PS2: maybe try changing `if (Math.Sqrt(distance) > (e.Value.Texture.Width / 2 + e2.Value.Texture.Width / 2))`

into

`if (distance > ((e.Value.Texture.Width * e.Value.Texture.Width ) / 2 + (e2.Value.Texture.Width * e2.Value.Texture.Width) / 2))`. while this won´t be the source of your problem it should increase speed a bit ;)
> 1 votes

# Answer
The issue is definitely the N^2 order of complexity. My suggestion is to combine octrees and approximations to avoid as much computation as possible. Some areas where approximation could be used are:

* If m/r^2 is too low, ignore the contribution as too small.
* Any masses within a sufficiently small area, sufficiently far away, can be considered a single mass.

I don't quite have an algorithm yet, but an octree would allow you to ignore a whole node that contributes too little, and also would allow you to treat a concentrated enough node as a single mass without exploring any deeper. "Concentrated enough" could be evaluated in many ways, but a simple formula might just be the area of the node divided by the distance to the node.
> 0 votes

# Answer
This answer is similar to the quad/ oct tree ideas, but not quite the same.

I suspect that there is potential for a massive gain by re-evaluating the force vectors between pairs of bodies based on their proximity.

That is, have each body maintain a priority list of forces applied by each other body. \[ This is not really that much storage for a few hundred bodies.\]

Having computed the distance, also compute the relative velocity and determine a "good for" time for the force. For example, a force is good as long as its direction does not change by more than 1e-5 radians or its relative distance by more than 1e-5.

```
class Force
    {
        public Vector2 force;
        public Time    validUntil;
        public Entity  otherBody;
    };

```

Then in `Update`, remove those `Force`s from the head of the priority queue whose `validUntil` has expired (less than current simulation time). For each of these subtract the force from that currently on the Entity; recompute the force with the `otherBody`; add that back to the Entity; compute the `validUntil` and re-insert.

This should vastly reduce the number of times distant objects recompute their force. In fact, you should find that two distant effectively exert constant force on each other in a natural way.

A second issue applies to nearby objects. Use the equivalent of `s = ut + at^2/2`:

```
Position oldP;
Velocity oldV;
Acceleration a;
Time dt;

Velocity newV = oldV + dt*a;
Position newApprox = oldP + dt * oldV + 0.5*dt*dt*a;

```

This will give you much better behavior than your current expression, allowing you to increase `dt`.

When building a gravity model, I like to apply various tests.

The simplest is to check that you actually get a circular orbit for something like an Earth-Sun system.

More sophisticated is to compute things like total momentum and total angular momentum and verify that these remain sufficiently constant.
> 0 votes

# Answer
The fastest code is code that doesn't run.

**Assumption:** The realistic gravity is almost surely for objects that are dynamic (spacecraft), where the planets are likely not interacting with each other to cause disturbances (such as our Solar System). Thus, if you have no rogue stars / planets knocking things out of orbit, consider:

**Solution:** Compute the stable orbit of each moon to its planet, and each planet to its star. You could use Kepler's laws of planetary motion, or even better, assume circular orbits, and just compute the speed required for orbit. Dynamic objects can still use the real gravity formula, so you could recreate the Apollo missions to the Moon, for example.
> 0 votes

---
Tags: xna, c#, physics, gpu
---


# Question
Title: Weird effect during rendering pixel art in Unity
I am building a top-down 2D game in Unity engine. I have made a house on my own but when I try to render it in Unity, it shows weird effect when camera moves.

See the roof of the house:

I want the roof to look proper and not this weird effect. How can I solve this? Is this an issue in art or renderer?

FYI, I have made this house in MS Paint and saved it as a PNG file.

* The original image is of size 256x256.
* PPU is set to 100 (default in Unity).
* Compression is set to None.
* Filter mode is Point (no filter).
* Orthographic camera size is 5.

# Answer
> 2 votes
At an orthographic camera size of 5, you'll show 10 units of the world from the top of the screen to the bottom.

If each unit has 100 texels of texture data (PPU/pixels per unit), then that's 1000 texels you're trying to pack in vertically.

That means you'll only get clean 1:1 pixel rendering if your window or full-screen monitor has a vertical resolution of *exactly* 1000. If you're viewing this in the Game window in Unity on a 1080p or smaller screen, you're probably trying to cram more sprite texels into the view than you have screen pixels to display them, so some have to get skipped. This leads to the shimmering distortions you see, for the reasons I detail in this answer.

If we want to achieve a similar look while getting pixel perfect display, we need to create the image to match the display resolution it will be shown on.

Let's say you like the current look where the 256-texel-tall house occupies about a quarter of the height of the 1000-texel-tall camera view.

If we assume the game is made to be played at 1080p, then we should make the image about 1080/4 = 270 texels tall. And we should make the PPU 108 so that 10 units of world space exactly matches 1080 pixels of screen space.

Or you could keep your 100 PPU, and zoom the camera out to size 1080/100/2 = 5.4

Alternatively, if you want to target a 720p resolution, a quarter of that would be a 180 texel tall house image. You'd then make your PPU 72 at camera size 5, or keep the 100 PPU and 3.6 camera size.

If you want to support both 1080 and 720p, that's harder, but can be done with certain specific texel sizes and scaling ratios or swapping between alternative sets of assets.

Regardless of which one of these you choose, you'll still see shimmering when previewing the game in a window smaller than the full-screen size you calibrated for. Such is the challenge of pixel perfect visual styles.

If you're willing to sacrifice pixel perfection, you can...

* Change your sprite filtering to "Bilinear" or "Trilinear" to blend pixels instead of skipping them.
* Click "enable mipmaps" in the sprite texture's import settings to auto-generate down-scaled versions of the texture to sample when displaying it smaller than its native size.
* Avoid 1-pixel-wide lines and details in your images, since these will tend to get blurred out when scaling the art.

You can also use custom pixel art scaling shaders that give a nicer result than the GPU's built-in linear sampling, especially if you're scaling up the images by at least 2x. There's not much you can do when scaling down, since you just don't have enough screen pixels to draw all the detail into, and some has to get lost somewhere. For this reason, you usually want to err toward smaller-resolution sprites if you want that crisp pixel art look at a wider range of resolutions, then scale it up for display.

---
Tags: unity, 2d, rendering, top-down
---


# Question
Title: UIElement button does not work when clicked
I have a small issue with my UI. Whenever I click a button on my pause menu ui nothing happens even when I hover over the buttons. However, in my main menu scene, the UI works without any problems. Comparing the code side by side they are pretty much identical. I am also using the UI toolkit for my UI instead of the older UI system.

```
public class PauseMenuUIDocumentManager : MonoBehaviour
{
   private static VisualElement pauseMenuContainer;
   private Button mainMenuButton;
   private Button settingsButton;
   private Button quitToDesktopButton;

   public static VisualElement PauseMenuContainer
   {
      get => pauseMenuContainer;
      set => pauseMenuContainer = value;
   }

   private void Start()
   {
      var root = GetComponent<UIDocument>().rootVisualElement;

      pauseMenuContainer = root.Q<VisualElement>("Background");

      mainMenuButton = root.Q<Button>("MainMenuButton");
      settingsButton = root.Q<Button>("SettingsButton");
      quitToDesktopButton = root.Q<Button>("QuitToDesktop");

      mainMenuButton.clicked += MainMenuButtonOnclicked;
      settingsButton.clicked += SettingsButtonOnclicked;
      quitToDesktopButton.clicked += QuitToDesktopButtonOnclicked;

   }

   private void QuitToDesktopButtonOnclicked()
   {
      Application.Quit();
   }

   private void MainMenuButtonOnclicked()
   {
      Time.timeScale = 1f;
      GameManager.LoadScene("MainMenu");
   }

   private void SettingsButtonOnclicked()
   {
      throw new NotImplementedException("This feature will be implemented later down the line");
   }
}

```

Here is my game manager script that actually shows the pause menu:

```
if (Input.GetKeyDown(KeyCode.Escape) && gameIsPaused == false && gameCanBeUnPaused == false)
      {
         PlayerMovement.MovementEnabled = false;
         gameIsPaused = true;
         Time.timeScale = 0f;
         StartCoroutine(CheckIfGameCanBeUnPaused());
         print("The game is paused");
         OpenPauseMenu();
      }

```

```
private void OpenPauseMenu()
   {
      PauseMenuUIDocumentManager.PauseMenuContainer.style.display = DisplayStyle.Flex;
   }

```

# Answer
Well, I found the problem. The problem was that you CANNOT have two UI documents active in the same scene that overlap, and if you do you have to disable the other one before you can interact with the other UI elements.
> 0 votes

---
Tags: unity, unity-ui, ui-toolkit
---


# Question
Title: Objects rendering only on editor, but not on build (they get invisible)
Everything works fine in the editor, but when I build the game, none of the objects in the scene are rendered, and only the skybox and UI text is visible. But although they aren't appearing, they are working as normally (i.e. these objects' triggers work normally when the determined event occurs, like for example, colliding to a specified object, or in other words, they are invisible).

I searched for this issue but didn't found any answer. Could it be my cheap computer's fault (Intel Celeron without an external graphics card)?
In editor game mode:
In buit game:
I ran both the editor and the built game in the same quality, and also tried to run it in Fastest quality, but no, it made no difference in the built game.

Also, there is no object tagged with "Editor only", only one have a custom tag and all the others are "Untagged". And the camera's culling mask is set to "Everything".

The result is the same either for web or Windows.

---

**Edit:**

OK, I built for Android and the objects render normally. So, I'm not completely sure, but probably it's my PC that can't render the objects, because both building for web plugin and desktop have this disappointing result, but for Android it works perfectly (even the shadows, which wasn't being cast in the editor), so...

# Answer
OMG!!!! It really worked :D The problem was shader, the default shader that unity provide for our game objects...Just change the shader from standard shader to legacy shader....then all of those game objects that were invisible will be visible :D Hope this works 4 ya :D

Cheers......
> 0 votes

# Answer
If anyone facing the same problem and as the OP said can do it but if you want to keep the same shader. **Goto -\> Project Settings -\> Graphics -\> Scroll down -\> Find Tab "Always Included Shaders" -\> add your shaders there which were not visible**
> 0 votes

---
Tags: unity, rendering
---


# Question
Title: Blender model imported into Unity has extra face
I created a very simple model in Blender that I exported as a .fbx and imported into Unity. After fixing normals/textures/etc, everything looks fine, except that the Unity mesh has an extra edge and face. The dormer polys that appear with an extra face are all duplicates, which would explain why it appears on every one.

Blender:  Blender Model that looks like it should

Unity:  Unity Model with extra face

Does anyone know how to fix my fbx export so that the extra face does not appear in Unity?

# Answer
Game engine renderers draw everything in triangles. So when importing models that contain polygons with more than three sides, the importer has to convert them to triangles. These import routines often prioritize speed over artistic perfection, since where it matters, artists can triangulate the geometry themselves to get the exact look they want. That means sometimes the algorithm will make a bad choice of which three vertices in the polygon to emit as a triangle.

Here, it triangulated the sides of the dormers like this:

When what you want is like this:

What you can do is go back to the source model in Blender and add an edge along the desired triangulation split, by using "Connect Vertex Pairs".

You should apply these splits anywhere you have a concave vertex, to ensure you're sending exclusively convex polygons through the import pipeline. Those will be handled much better, as many efficient algorithms are only correct for convex polygons.
> 1 votes

---
Tags: unity, blender
---


# Question
Title: 3d model has this gap between head and body?
My 3D model is separated into a head and a body, but I’m encountering gaps between them. Although it appears to be a lighting issue, even after removing the material, the gaps persist. Do you have any ideas on how to address this?

# Answer
> 1 votes
It has something to do with the normals and the shading of the engine itself. There's really not much you can do about it, unless you merge the two meshes together (which is not what you want).

There's an answer here that suggest using Blender's Data Transfer modifier to transfer vertex normals from the full/uncut model to a separated version of it, but for that you'll need the original, not-separated-yet, full model.

Keep in mind that this is a very common thing and, usually, these kinds of seams are made in occluded or barely visible areas for the same reason.

---
Tags: unity
---


title: UE5 - Add texture to landscape

text:
# Question
Title: UE5 - Add texture to landscape
I created a terrain in gaea and exported it to UE5.

Then I created a new material with this texture which is for my whole landscape:

Material settings:

The preview above is already looking good.

But this is the result:

How can I fix it?

# Answer
I fixed it by replacing the **LandscapeCord** (Landscape Layer Coords) Node with a Texture Coordinate node.

I had to experiment with the value UTiling and VTiling until the texture was matching with my terrain. In my case I had to use very low values, because my terrain was scaled to X 700 Y 700 Z 700.

Result:
> 1 votes

---
Tags: unreal-5
---


# Question
Title: How does bullet physics filter 4+ contacts in GJK?
If the bullet GJK (Convex vs convex) collision algorithm has more than four penetrating points, then how is it filtering that down to the four it needs?

*What I've tried*

* *Staring at the code, but I get confused at this part.*
* *I figure it keeps the deepest penetration somehow*

# Answer
It uses a heuristic which selects which point of the existing four that should be replaced by the new point. This heuristic function produces a value that's proportional to an approximation of the contact surface area, i.e. two triangles that form the quadrilateral with the four contact points. It goes over each possibility, replacing one point at a time by the new point and finds which configuration maximizes contact area. And yes, it also prioritizes the deepest point. This helps prevent the deepest from being replaced which would result in visible penetration.

Another possible heuristic is to maximize the surface area of the tetrahedron formed by the four points, which is what I do in my physics engine and I get satisfying results. By consequence, this method chooses to keep the deepest point since it results in a bigger tetrahedron with larger surface area.
> 0 votes

---
Tags: c++, physics, python, bullet-physics
---


# Question
Title: How would you find the most optimal path in the the traditional snake game?
I was thinking about how to implement snake today, in particular, how to ensure the snake moves optimally from one target to the next.

This seems like a shortest path problem, but it's a bit tricky because you have to keep track of the snake's body positions for every node in the BFS traversal, which could take up a lot of memory. Is there a better approach than what I'm envisioning here?

# Answer
The problem isn't getting to the apple, it's making sure you have an escape route *after* eating the apple.

\[Edited for clarity, comments may not make sense\]

What you're looking for is a ***Hamiltonian cycle*** (a single, continuous path that passes through every square on the board). It's the only way to guarantee you won't trap yourself, but finding an optimal one is non-trivial.

The YouTube channel AlphaPhoenix has a fantastic video detailing the various problems and optimisations.

AlphaPhoenix: How to Win Snake

At a high level, you need to ensure you always have a Hamiltonian path, so you can never get stuck.

Then you need to

* Aim for the apple (whilst preserving a valid path)
* Minimise the amount of time you spend filling up space "waiting"
* Try to avoid scenarios where you have to do a whole circuit of the board to progress

To explain why you always need the cycle, here's part of two frames from the linked video

To start with, heading straight to the apple makes sense.

But when you actually turn in to bite it, you can trap yourself in a dead-end.

If you're using a pure BFS approach, the obvious move is "down", directly to the closest apple.

Unfortunately, that would be a game-over situation in 2 more moves.

For a BFS-approach to work, you'd need to find paths that lead not only to the apple but also to **every** free square on the board (accounting for snake movement in the interim) and track/choose the one with the shortest distance to the apple.

To be explicit: Any path that can't also reach every square *after collecting the apple* has to be rejected *before* you can pick a safe path.

That means your breadth-first search has to reach maximum depth in all cases.

I believe you'll find that's computationally infeasible in anything even close to real-time.
> 5 votes

# Answer
For every node occupied by the snake, you can compute in how many steps it will be freed. So if you keep track of how many steps you are doing in your path search, you can compare that to know if the node would be occupied when the snake reaches it.

Addendum: You might be worried about nodes occupied by future movement of the snake, but if your reach algorithm does not create paths that repeat nodes to begin with, then that is not a concern.
> 2 votes

---
Tags: snake
---


# Question
Title: Reduce Repeating geometry (e.g., vegetation) size and memory in unity
I have a large urban area in 3D (Unity), where some models or geometries are repeatedly placed. For instance, we have vegetation objects like trees, grass, or bushes that are positioned in various areas on the floor. These objects share the same geometry, but sometimes they have different sizes when placed in 3D.

My question is whether the size of these repeated geometries is directly proportional to their usage. In other words, as I place more trees with their Levels of Detail (LoD), the overall memory size and player size increase. Is there any way to restrict the size of the player or memory, given the context that I have a large number of objects that are repeating?

Edit: Here is the memory screenshot:

# Answer
> 2 votes
When you have several copies of a mesh in your scene, Unity does not store several copies of the complete mesh data.

Only one mesh asset is stored in memory or in your build (possibly containing multiple LODs), and the instances just reference this asset. These instance objects store their own distinct position/orientation/scale data (a matter of bytes' worth), but this is applied "just in time" on the GPU during rendering instead of demanding a whole transformed copy of the vertex data.

So, generally speaking, placing more copies of an object does not increase the amount of memory used to store their geometry.

The exception to this is if the objects get baked together as a batch to reduce draw calls.

If these objects are marked as "static", Unity can bake several copies together into one larger mesh to store in the scene, reducing draw calls for faster rendering, at the cost of larger memory/build size.

Batching can also be done dynamically, which would increase video RAM use but not increase build size.

You can disable batching on the material the vegetation uses if you want to prevent this from happening, even when the engine calculates that it would be advantageous to your framerate.

If the vegetation items are using the exact same mesh and the materials used support instancing, then the engine should render them with instancing instead of dynamic batching anyway, since that achieves similar draw call reduction without the same memory overhead.

---
Tags: unity
---


title: Destroy doesn't destroy GameObject

text:
# Question
Title: Destroy doesn't destroy GameObject
I was trying to create a debug view for my Water object in my Unity application. The problem is that I generate the water at runtime, which makes it impossible to see what it looks like in the editor mode. To resolve this, I created a script that draws a simple sprite representing my water:

```
using System.Collections;
using System.Collections.Generic;
using Unity.VisualScripting;
using UnityEngine;

[ExecuteInEditMode]
public class WaterEditor : MonoBehaviour
{
    [SerializeField] Sprite waterSprite;

    GameObject debugWaterObject;
    SpriteRenderer tileRenderer;
    Water water;

    void OnEnable() {
        water = GetComponent<Water>();
    }

    void Update()
    {
        if (Application.isPlaying) {
            Debug.Log("Destroying debug object");
            Destroy(debugWaterObject);
            return;
        } else if (debugWaterObject == null) {
            Debug.Log("Creating debug object");
            debugWaterObject = new GameObject("Water Debug Object");
            debugWaterObject.transform.SetParent(transform);
            debugWaterObject.transform.localPosition = Vector3.zero;
            tileRenderer = debugWaterObject.AddComponent<SpriteRenderer>();
            tileRenderer.sprite = waterSprite;
            tileRenderer.drawMode = SpriteDrawMode.Sliced;
        }

        tileRenderer.size = new Vector2(water.width, water.height);
    }
}

```

The idea is that I create a debug object in editor mode and then destroy it in play mode. However, for some reason, when I run my application, I can still see the object in the editor:

I'm pretty sure that `Destroy(debugWaterObject)` is called, and the object is not recreated in play mode. It seems that it is not being destroyed. I haven't been able to find any explanation for that. Why could this happen?

# Answer
When you set a debugger breakpoint\* in your script, then you will see that the `debugWaterObject` becomes `null` as soon as you switch from game mode to play mode.

This has something to do with how Unity re-initializes objects in the scene on game launch. If you want changes to inspector-exposed variables made by edit mode scripts to persist, then it's not enough to just change the variable. You have to go through the serialized property API.

But there is probably a much easier solution to the problem: Just add this little script to the debug object that will cause it to self-terminate as soon as you enter play mode:

```
using UnityEngine;

public class SelfDestroyOnAwake : MonoBehaviour
{
    void Awake()
    {
        Destroy(gameObject);
    }
}

```

Note that this script does not have anything that causes it to execute in edit mode, so it will only execute in play mode.

In order to attach a script to an object that was just created via `new GameObject`, do this:

```
debugWaterObject.AddComponent<SelfDestroyOnAwake>();

```

<sub>\*If you don't know what debugger breakpoints are, then I really recommend to learn how to use the debugger of your preferred code editor with Unity. It will help you solve about 95% of programming problems yourself that would otherwise require you to ask on the Internet.</sub>
> 1 votes

# Answer
You're working in the Editor, and using `[ExecuteInEditMode]`. It's better to use `EditorApplication.isPlaying` instead of `Application.isPlaying`. While both do essentially the same thing, one was made specifically for Editor stuff, and the other one works better for build applications (even though it should work in Editor as well, but sometimes it can behave weirdly).
> 0 votes

---
Tags: unity, gameobject
---


title: Save game data in png file

text:
# Question
Title: Save game data in png file
I want to save my game as a PNG file. Which parts should I include in the file?

Should I include the alpha channel, EXIF data, or something else?

# Answer
> 0 votes
There is the code you can modify outPng as you wish (Texture2D have lot of useful methods) and then save it as png file anywhere you want:

```
Texture2D outPng;
var toPng = outPng.EncodeToPNG();
File.WriteAllBytes(Application.dataPath + "/filename"+ ".png", toPng);

```

---
Tags: unity
---


title: How can I fit a tree graph into a grid?

text:
# Question
Title: How can I fit a tree graph into a grid?
I have a tree graph that I'd like to fit into a grid, the result being a grid-based maze that adheres to the tree graph. Are there any good maze algorithms that are able to start with a known structure?

Here's a crude example:

The child nodes do not have to be immediately adjacent to their parent in the grid, but must maintain the same reachability. This is reflected in the black "dummy" node in the image.

The basic concept is to build a node tree reflecting the "logic" of a space, then building a reasonably compact, grid-based "maze" that maintains that logic.

# Answer
> -2 votes
You cannot fit a tree graph into a 2d grid because of one simple reason - one vertice can have 8+ connections in the 2d grid you have only 8 bordered cells. Even if you limit the nodes connection to for example only a maximum of 2. You will shortly get dead end situations very fast.

---
Tags: procedural-generation, tree, maze
---