Delegation and Ad-hoc polymorphism in Kotlin

CAUTION: This post got somewhat long :/ TLDR: You can effectively use Kotlin's delegation if you want to mimic ad-hoc polymorphism.

I was always fascinated by ad-hoc polymorphism. The clear separation between data and behavior that can for example be achieved with tools like Scala's type classes, is especially useful when combined with data oriented design, which is important for game development as well for example.

I realized, that the usefulness depends heavily on how this feature can be integrated and supported by the programming language you work with.

For example in Go, you don't have to implement an interface explicitly - if your 'class' (Go doesn't have classes) satisfies the contract of the interface, it is virtually implemented. That means you can safely pass your instance of your class into a method that expects an interface. I like that this is called static duck typing. This is a form of structural typing, because your instance is typed by parts of its definition. Structural typing has many advantages, but also the disadvantage that code can break or fail at runtime, when said interfaces change visibly or invisibly. Also, there's the potential of naming clashes, for example if two interfaces have methods with the same name/signature. Although I don't know anyhing about the internal implementation of Go's structural typing, I suggest that the whole system works without creating wrappers under the hood.

In languages like Java and Scala, we don't have this luxury, or rather we have to solve slightly different problems here. I find Scala's solution a very good one - but I don't know too many comparable others :) The type classes combined with implicits are a very good example of how to integrate this feature into a statically typed language (This is a very nice post that pretty much answers all questions about how those type classes and implicits in Scala work).

And here's the big but (and I can not lie..): The feature is very infamous by people that don't use Scala and even infamous by some people who do use it. My humble opinion is, that it boils down to the old problem: As a programmer, you read more code than you write. That should imply, that the ability to read code more easily is more important than the ability to write code easily. I would like to correct this statement slightly: It's more important to be able to easily read and understand what's happening. Very concise code is nice to read, because it hides a large amount of information - but there is a thin red line that should not be crossed when hiding information. Problem here is, that this is very subjective to a degree. One of the biggest critics to Scala is the complex implicit resolution, where people really struggle to understand it and even the compile times suffer drastically from it. This weakness is so clearly a problem not only for mediocre programmers, non-library developers but also for code quality of a project in general, that the Kotlin creators decided to leave ad-hoc polymorphism out of the language until now.

At the time of writing this, similar blog posts to my thoughts were created here and here. And in fact, even after reading the whole language improvement suggestion for ad-hoc polymorphism, I'm not quite sure if ad-hoc polymorphism without something comparable to Scala's implicits makes sense at all. Here's a small example of a situation where the usage of ad-hoc polymorphism would be appropriate: You have an interface and some implementations of this interface. The interface is consumed by some methods, one of them is someFrameWorkFunction:

interface MyInterface {  
    fun myInterfaceMethod()  
}  
class MiOwnImplementation : MyInterface {  
    override fun myInterfaceMethod() = println("This is my own implementation")  
}  
fun someFrameWorkFunction(parameter: MyInterface) = parameter.myInterfaceMethod()  
fun main(args: Array) {  
    someFrameWorkFunction(MiOwnImplementation())  
}  

Everything is fine until you have to integrate code that's outside of your control. As the following class, that may already have the functionality you need implemented, but with a wrong method signature and without your interface (because where should people get your interface from...):

class ForeignImplementation {  
    fun printSomething() = println("This is a foreign implementation")  
}  

Irrelevant which solution you take to integrate this foreign implementation, one thing is for sure: you need a description how the needed functions are implemented, hence a mapping from interface methods to implementation methods.

This could do the job in Kotlin, nothing fancy.

class MyFacade(private val impl: ForeignImplementation) : MyInterface {  
   override fun myInterfaceMethod() = impl.printSomething()  
}

Afterwards, we can use our implementation like this. Alternatively, we can use Kotlin's equivalent of an anonymous class, an object:

fun main(args: Array) {  
   someFrameWorkFunction(MiOwnImplementation())  
   someFrameWorkFunction(object : MyInterface {  
     private val impl = ForeignImplementation()  
     override fun myInterfaceMethod() = impl.printSomething()
  }
}

With an implicit resolution algorithm, one could write

someFrameWorkFunction(ForeignImplementation())  

instead of explicitly instantiating one's own facade.

The question here is: Is the implicit resolution worth the hassle that one now has to search for the conversion definition? Is the example with the explicit conversion that much worse readable? In my opinion, until now, there's no reason to not state the conversion explicitly. Only with taking the feature even further, it makes sense to have it - for example because you are used to using contextual objects as implicit parameters, as they are embedded in the language, like in Scala. For example it's possible to provide default implementations that can be imported by the user of your library. Without such a feature, one would have to provide overloads of a method that takes types as parameters. Kotlin won't benefit from it, instead it would be an artificial feature that is limited to one situation.
Swift on the other side allows for extensions, that can have an existing class implement an interface with some limitations I don't know in particular. Extensions are automatically available through module import. So they are somewhat comparable to what Scala can do, because your module can contain all the default extensions and make them available for the user.

In general, the separation of state and behavior could become the default option and ad-hoc polymorphism could be the default over parametric polymorphism. But on the JVM, you will have to pay for the wrapping class, so this is probably not the most wise idea. Extension functions on the other hand seem to extend a class's interface but does it via syntactic sugar and static dispatch. That means the extension can be imported on the callee's side, whereas class extensions or type classes are chosen by the caller.

So let's think about a more complex scenario. The interface our framework method accepts is a more complex one, that extends the List interface and provides a getLast() method that doesn't throw an exception if the list is empty, but returns a nullable reference. This can be a default implementation that uses an abstract property. Additionally, a real interface method is declared for prettyprinting, that classes have to implement.

interface MyList<T> : List<T> {  
   val list: List<T>  
   fun getLast() : T? = if (!list.isEmpty()) list.last() else null  
   fun prettyPrint()
}

Since one can only delegate to constructor parameters and new instances in Kotlin, there is no way to have MyList provide default implementations for all List methods just by delegating to the abstract property list. This limitation prohibits using a simple inline object declaration in a method that consumes a MyList interface because you would have to implement all methods of the List interface or create a local list outside of the statement.
A solution would be to create a simple Implementation (as one could and should typically with heavy use of delegation), that implements the List interface by itself with delegation, like:

class MyListImpl(override val list : List<T>) : MyList<T>, List<T> by list {  
   override fun prettyPrint() = println("Pretty: " + super.toString())  
}

So the framework method can be called like

someFrameWorkFunction(MyListImpl(emptyList()))

While this is not ad-hoc polymorphism by definition, under the hood it's equivalent to comparable solutions. Delegation can help to overcome many of the pain points when the need to satisfy interfaces with existing classes emerge. As for a general purpose usage of type classes, one has to keep in mind that delegation has a small runtime overhead, as it creates objects and delegates method calls.

Another very clean solution would be to use scopes extension methods to achieve the same thing. Usage of with can bring extensions defined on a interface into scope. Using a singleton would prevent us from creating objects, but obviously, one would have to pass the extension provider explicitly as a parameter.

interface ExtensionProvider<T> {
    fun T.customExtensionMethod()
}
object IntExtensionProvider : ExtensionProvider<Int> {
    override fun Int.customExtensionMethod() = println("Custom method prints: " + this)
}
fun <T> someFrameWorkFunction(list : List<T>, extensionProvider: ExtensionProvider<T>) {
    with(extensionProvider) {
        list.forEach { it.customExtensionMethod() }
    }
}

fun main(args: Array<String>) {
    someFrameWorkFunction(listOf(1,2,3), IntExtensionProvider)
}

And now I hope that I didn't confuse the wording of all these things :)

glDrawElementsBaseVertex demystified

In days of Vulkan and DX12, I started investigating how much time my cpu spends on pushing the OpenGL draw calls I need. Turns out: too much if you ask me. On my desktop machine, there's no problem at all, but on weaker hardware, it might be relevant. And at all, my CPU should not have work to do at all, or at least I don't want it to spend more time on pushing a command than the command actually takes to complete on the GPU.

One very evil thing you mostly can not avoid is vertex buffer binding. If you want to have it flexible, every model could have its own vertex buffer, which you can unload, modify and stuff. However, most of your scene contents share a common vertex format - for example you mostly have position attributes, normals and texture attributes. Heavier stuff like bone matrices and material parameters could be unload to seperate buffer objects and accessed via an index, so using a shared vertex and index buffer for all your scene's geometry really really should pay off.

My way was using a pinned memory buffer (aka persistent mapped) that automatically doubles when too small. Registering a new model in the scene simply appends the unique vertex attributes of this model to the global buffer. The same for the indices. Drawing could now be done with glDrawElementsBaseVertex.

Turns out there's a lot of confusion about the usage of this beast and some people even can't figure out how it is different from glDrawElements with a index buffer offset passed. The magic is: the base vertex attribute of glDrawElementsBaseVertex adds a value to the contents of your index buffer. Indeed, it's not an offset that is used to retrieve the current index from the index buffer, it is an offset that is actually added to the value of your index. Why? Because this way, you don't have to take care of adjusting indices by yourself when appending indices to a global index buffer. Here's an example:

You have a plane, constisting of two triangles - 4 unique vertices (the corners) and 6 indices (2 triangles a 3 vertices). After you put those in your global buffers, you want to add another plane. If you append the new plane's 4 unique vertices to the global vertex buffer, you have 8 vertices in it. The first vertex can be accessed with index 4+0, the second one with 4+1 and so on. This offset has to be added to the indices of the new plane, or you can't use its indices with the global buffers. Since this is dumb work, OpenGL offers glDrawElementsBaseVertex. In this case, one could use it as follows to draw your two planes:

glDrawElementsBaseVertex (GL_TRIANGLES, 3*2, GL_UNSIGNED_INT, 4*0, 0);
glDrawElementsBaseVertex (GL_TRIANGLES, 3*2, GL_UNSIGNED_INT, 4*4, 4);

where the second parameter is the index count - 2 triangles times 3 indices per triangle, the fourth parameter is the byte offset into the index buffer and the last parameter is the value that should be added to each index value of your current draw call.

Puh, took me a while. Now we're prepared for indirect drawing.

Realtime Importance Sampling with Boxprojected G-Buffer CubeMaps for Dynamic Global Illumination

Last year, I wrote my masther's thesis about global illumination effects in realtime rendering engines. Since I haven't yet published any infos, because I didn't know how, I finally do it now. The result of the thesis was an implementation of a custom deffered rendering engine with LWJGL.

Addiotionally, I used something that is called boxprojection with cubemap datastructures. Furthermore, I modeled proxy objects (boxes) that I call probes - they are axis aligned bounding boxes with a corresponding cubemap, very much like a dynamic environment map. Instead of just one texture for a snapshot of the environment, I attached multiple textures for the exact same purpose that multiple textures are used for in G-Buffers for deferred rendering. Pre-Rendering all positions and material attributes of a whole level leaves us with the need to evaluate the lighting, when lighting conditions change. That is much cheaper than actually render the complete (environment) map again, like with traditional environment mapping. Additionally, the first and second pass shaders from the deferred rendering can be reused, instead of having additional forward shaders, as with regular environment mapping.

At this point, one would be able to use those environment maps for perfect reflection mapping. Can be used for all dynamic and static objects, reflects static objects with dynamic lighting. But that's not enough; there's something called realtime importance sampling, that could use prefiltered cubemaps, to have a complete lighting model covered - that means specular and diffuse reflections with arbitrary lighting models. One just has to calculate the mipmaps for the cubemaps and everything will work. Another possible tweak is to precalculate the radiance for each cubemap and save it different roughness values in the mipmaps. Have a look at Unreal Engine 4's implementation. Thats how I implemented it to avoid the costly importance sampling in trade of quality.

Since probes have to be placed within the level, on needs to blend between multiple probes. I implemented an algorithm from Sebastien Lagarde, similar to his approach in the game Remember Me.

The result is pretty nice global illumination in high framerates with the possibility to alternate probe update over time, stream probes etc. It can run on my GTX 770 with framerates above 150 fps in the sponza scene - depending on additional quality settings, like multiple bounces etc. Here's a screenshot of what could be done, again, completey dynamic lighting, static geometry. Dynamic geometry would take more ressources.

I will provide more info, if anybody is interested.

Bindless texture with LWJGL

The classic bound texture paradigma is so 1990. But getting bindless textures to work is not that easy, especially when you're using something other than C or C++. For all the LWJGL or Java users out there, here are some notes that may help you removing the classic texture pipeline from your engine. I think you can read about the technique in the internet, so I'll keep it mostly short.

First of all, you need a handle (some kind of pointer again, but don't think of it as a pointer, yucks) for a given texture.

 long handle = ARBBindlessTexture.glGetTextureHandleARB(textureID);  

Afterwards, the handle has to be made resident. I think that's something you need for the combination with partially resident textures.

 ARBBindlessTexture.glMakeTextureHandleResidentARB(handle);  

This was the easy part. Now, you have to use the handle in our shaders somehow. The easiest way would be to use it as a uniform.

 ARBBindlessTexture.glUniformHandleui64ARB(location, handle);  

Inside your shader, you have to use the handle. But what datatype should one use? Maybe I missed something elementary, but  there's only one proper way, namely use a datatype made available through an nvidia extension. Since bindless textures are available through an extension as well, here are both calls that you (probably) need:

 #extension GL_NV_gpu_shader5 : enable  
 #extension GL_ARB_bindless_texture : enable  

And now, you can use tha datatype uint64_t. So your uniform would be a uint64_t.

That would work. But most probable, you want to have your data in a uniform or storage buffer, probably together with some other data and datatypes. So here's what I did.

Use a DoubleBuffer (Java native buffer, available via BufferUtils.createDoubleBuffer(int size)) for your data. Since doubles are twice the size of a float, which is 4 byte, we have 8 bytes per texture handle, which is 64 bits, which is the same as a uint64's size, so that's enough. Now one has to take the generated handle's bits and put them into the buffer (for example a ssbo) as they are. This can be done like so:

 GL15.glBufferSubData(GL43.GL_SHADER_STORAGE_BUFFER, offset * primitiveByteSize, values);  

-
Where primitiveByteSize is 8 in this case. Since we use the underlying buffer as a DoubleBuffer, we have to provide a double value for the handle (or use it as a byte buffer, but nevertheless we need the correct bits or bytes). You can convert a Java long to and from a double like this:

 Double.longBitsToDouble(longValue)  

 Double.doubleToLongBits(doubleValue)  

Afterwars, the shader can take the value as a said uint64_t and cast it to a sampler. Sounds ugly, maybe it is.

 color = texture(sampler2D(uint64_t(material.handleDiffuse)), UV);  

That is the whole story, took me a while to figure it out.

Get normal for cubemap texel

Since I came across this problem and wasn't able to find an easy solution on the internet, I decided to write s small recipe to calculate normals when you want to do manual mipmapping/radiance convolution with cubemaps in OpenGL. I use compute shaders, so for geometry/vertex/pixel-pipeline, you could use layered rendering and other stuff.

First of all, the shader needs the current cubemap face index as a uniform variable. I recommend using the standard OpenGL indices (see link below).

Most likely, you are using the standard cubemap layout. If this is not the case, you have to change the vectors in my code. So with a given face index and a given texel position, the problem can be solved:




What happens here is that I calculate the pixel position in texture space with the help of the invoation position. The compute shader is invoked with cubemapfaceResolution.x/16, cubemapfaceResolution.y/16, 1. Knowing which (OpenGL) world axis the view direction of the virtual camera, facing the current cubemap side from the inside (cubemaps origin) is, the other two axis are the two orthogonal axes. These two axes' values grow with the texelcoordinates we already have. But therefore, they have to be remapped from 0 - 1 to -1 - 1. The resulting vector can be used to sample a cubemap as it is. Normalization could be unnecessary.

Using Go with eclipse

I like how different platfoms like Java, C++, build tools like maven, gradle etc. are integrated in eclipse via its extension mechanisms. So the first fight every tool that wants me to use it has to win is its eclipse integration. Because the usage of Google's Go with eclipse isn't a complete no-brainer, I want to share the way I did my setup. So here's a guide how you can setup Go on Windows, with eclipse luna.

1. Install your go distribution
   You can download your distribution from the official download page. The installation is quite easy. After completion, ensure that your environment variable GOROOT points to your Go folder. The variable GOPATH should point to your chosen workspace, in the means of where you want to place your Go projects. Or where you have any libs or other Go code. This sounds like an easy job, but seems to be confusing for half the internet, me included. It turns out that every directory in the go path has to have a well described structure, that you can find here. We will take another look later, when the run configuration in elcipse is confiured. You can check if Go is properly installed via a shell with "go version".
2. Install eclipse integration
   Within eclipse (luna) go to Help -> Install new software and use http://goclipse.github.io/releases/ as path. Chose the GoClipse project and install.
3. Create a Go project
   This is fairly easy: Restart your eclipse, chose File -> new Project -> Go Project . You could check the box for automatic main method generation. Now slow down, first chance to waste time ahead: You should create a subfolder in src because if you just place your first Go file in the source folder and try to execute it, you would get go install: no install location for directory as a response. Also not nice is that eclipse auto generates a main.go file and places it right in the wrong folder...Took me half an hour to figure out that not my Go installation is the cause, but that I placed the source file in the top source folder. Don't do that. Create a Go file, your main function if not already done.
4. Adjust your path
   As said before, the GOPATH variale shows your workspace. If you have several IDEs or several projects, it could be useful to use the run configurations to override the path. Therefore, open Window -> Preferences -> Go. This is where you could set a path for your eclipse executions if your default path is not the right one.
5. Add a debugger
   Probably the most interesting part. Since Go is a compiled language, you have to work with debug symbols. I think Go's compiler is based on the GCC, therefore you can use the GDB. On Windows, you could get trouble finding it, so here is your link. Install wherever you like it and afterwards, go back to your eclipse. Right-click your project and chose Debug Configurations. Select the Debugger tab and tell your IDE where your gdb.exe can be found. Uncheck the box Stop on startup at main because this won't work with your go program and apply the settings. Now you can use eclipse debugging as you know it, with breakpoints and stepping and stuff. Remember that go programs are not fully compatible to gdb, so there will be some issues. Let me correct myself: There will be many issues. Doesn't work very nice at all. But at least you can use it.