{"id":40,"date":"2013-08-30T02:51:13","date_gmt":"2013-08-30T02:51:13","guid":{"rendered":"https:\/\/blogs.scummvm.org\/richiesams\/?p=40"},"modified":"2022-05-22T20:18:05","modified_gmt":"2022-05-22T20:18:05","slug":"one-pixel-at-a-time","status":"publish","type":"post","link":"https:\/\/blogs.scummvm.org\/richiesams\/2013\/08\/30\/one-pixel-at-a-time\/","title":{"rendered":"One pixel at a time"},"content":{"rendered":"

Over the course of this project, the way I’ve rendered images to the screen has rather drastically changed. Well, let me clarify. Everything is blitted to the screen in exactly the same way ( OSystem::copyRectToScreen ), however, how I get\/modify the pixels that I pass to copyRectToScreen() has changed. (Disclaimer: From past experiences, we know that panorama images are stored transposed. However, in this post, I’m not really going to talk about it, though you may see some snippets of that in code examples) So a brief history:<\/p>\n

In my first iteration an image would be rendered to the screen as such:<\/p>\n

    \n
  1. Load the image from file to a pixel buffer<\/li>\n
  2. Choose where to put the image.<\/li>\n
  3. Choose what portion of the image we want to render to the screen. We don’t actually specify the height\/width, just the (x,y) top-left corner\n
    <\/div>\n
    <\/div>\n<\/li>\n
  4. Call renderSubRect(buffer, destinationPoint, Common::Point(200, 0))<\/li>\n
  5. Create a subRect of the image by clipping the entire image width\/height with the boundaries of the window and the boundaries of the image size<\/li>\n
  6. If we’re in Panorama or Tilt RenderState, then warp the pixels of the subRect. (See\u00a0post about the panorama system<\/a>)<\/li>\n
  7. Render the final pixels to the screen using OSytem::copyRectToScreen()<\/li>\n
  8. If we’re rendering a background image (boolean passed in the arguments), check if the dimensions of the subRect completely fill the window boundaries. If they don’t them we need to wrap the image so it seems like it is continuous.<\/li>\n
  9. If we need to wrap, calculate a wrappedSubRect\u00a0and a wrappedDestination point\u00a0from the subRect dimensions and the window dimensions.<\/li>\n
  10. Call renderSubRect(buffer, wrappedDestination, wrappedSubRect)<\/li>\n<\/ol>\n

    At first glance, this seems like it would work well; however, it had some major flaws. The biggest problem stemmed from the\u00a0Z-Vision technology<\/a>.<\/p>\n

    To understand why, let’s review how pixel warping works:<\/p>\n

      \n
    1. We use math to create a table of (x, y) offsets.<\/li>\n
    2. For each pixel in the subRect:\n
        \n
      1. Look up the offsets for the corresponding (x, y) position<\/li>\n
      2. Add those offsets to the the actual coordinates<\/li>\n
      3. Look up the pixel color at the new coordinates<\/li>\n
      4. Write that pixel color to the destination buffer at the original coordinates<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

        Let’s give a specific example:<\/p>\n

        <\/div>\n
          \n
        1. We want to render a pixel located at (183, 91)\n
          <\/div>\n<\/li>\n
        2. We go to the RenderTable and look up the offsets at location\u00a0(183, 91)\n
          <\/div>\n
          <\/div>\n<\/li>\n
        3. Add (52, 13) to (183, 91) to get (235, 104)<\/li>\n
        4. Look up the pixel color at\u00a0(235, 104). In this example, the color is FFFC00 (Yellow).\n
          <\/div>\n
          <\/div>\n<\/li>\n
        5. Write to color FFFC00 to (183, 91) in the destination buffer<\/li>\n<\/ol>\n

          The problem occurs when you’re at the edges of an image. Let’s consider the same scenario, but the image is shifted to the left:<\/p>\n

          <\/div>\n
          <\/div>\n

          Let’s skip to step 4:
          \nWhen we try to look up the pixel color at (235, 104) we have a problem. (235, 104) is outside the boundaries of the image.<\/p>\n

          So, after discussing the problem with wjp, we thought that we could let the pixel warping function ( mutateImage() ) do the image wrapping, instead of doing it in renderSubRectToScreen. Therefore, in renderSubRectToScreen(), instead of clipping subRect to the boundaries of the image, I expand it to fill the entire window. Then inside of mutateImage, if the final pixel coordinates are larger or smaller than the actual image dimensions, I just keep adding or subtracting image widths\/heights until the coordinates are in the correct range.<\/p>\n

          void RenderTable::mutateImage(uint16 *sourceBuffer, uint16* destBuffer, int16 imageWidth, int16 imageHeight, int16 destinationX, int16 destinationY, const Common::Rect &subRect, bool wrap) {\r\n    for (int16 y = subRect.top; y < subRect.bottom; y++) {\r\n        int16 normalizedY = y - subRect.top;\r\n        int32 internalColumnIndex = (normalizedY + destinationY) * _numColumns;\r\n        int32 destColumnIndex = normalizedY * _numColumns;\r\n\r\n        for (int16 x = subRect.left; x < subRect.right; x++) {\r\n            int16 normalizedX = x - subRect.left;\r\n\r\n            int32 index = internalColumnIndex + normalizedX + destinationX;\r\n\r\n            \/\/ RenderTable only stores offsets from the original coordinates\r\n            int16 sourceYIndex = y + _internalBuffer[index].y;\r\n            int16 sourceXIndex = x + _internalBuffer[index].x;\r\n\r\n            if (wrap) {\r\n                \/\/ If the indicies are outside of the dimensions of the image, shift the indicies until they are in range\r\n                while (sourceXIndex >= imageWidth) {\r\n                    sourceXIndex -= imageWidth;\r\n                }\r\n                while (sourceXIndex < 0) {\r\n                    sourceXIndex += imageWidth;\r\n                }\r\n\r\n                while (sourceYIndex >= imageHeight) {\r\n                    sourceYIndex -= imageHeight;\r\n                }\r\n                while (sourceYIndex < 0) {\r\n                    sourceYIndex += imageHeight;\r\n                }\r\n            } else {\r\n                \/\/ Clamp the yIndex to the size of the image\r\n                sourceYIndex = CLIP<int16>(sourceYIndex, 0, imageHeight - 1);\r\n\r\n                \/\/ Clamp the xIndex to the size of the image\r\n                sourceXIndex = CLIP<int16>(sourceXIndex, 0, imageWidth - 1);\r\n            }\r\n            \r\n            destBuffer[destColumnIndex + normalizedX] = sourceBuffer[sourceYIndex * imageWidth + sourceXIndex];\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
          With these changes, rendering worked well and wrapping\/scrolling worked well. However, the way in which Zork games calculate background position forced me to slightly change the model.<\/p>\n
          Script files change location by calling “change_location(<world> <room> <nodeview> <location>).\u00a0location\u00a0refers to the initial position of the background image. Originally I thought this referred to distance from the top-left corner of the image. So for example, location = 200 would create the following image:<\/p>\n
          <\/div>\n
          However, it turns out that this is not the case.\u00a0location\u00a0refers to distance the top-left corner is from the center line of the window:<\/p>\n
          <\/div>\n
          Therefore, rather than worry about a subRect at all, I just pass in the destination coordinate, and then try to render the entire image (clipping it to window boundaries):<\/p>\n
          void RenderManager::renderSubRectToScreen(Graphics::Surface &surface, int16 destinationX, int16 destinationY, bool wrap) {    \r\n    int16 subRectX = 0;\r\n    int16 subRectY = 0;\r\n\r\n    \/\/ Take care of negative destinations\r\n    if (destinationX < 0) {\r\n        subRectX = -destinationX;\r\n        destinationX = 0;\r\n    } else if (destinationX >= surface.w) {\r\n        \/\/ Take care of extreme positive destinations\r\n        destinationX -= surface.w;\r\n    }\r\n\r\n    \/\/ Take care of negative destinations\r\n    if (destinationY < 0) {\r\n        subRectY = -destinationY;\r\n        destinationY = 0;\r\n    } else if (destinationY >= surface.h) {\r\n        \/\/ Take care of extreme positive destinations\r\n        destinationY -= surface.h;\r\n    }\r\n\r\n    if (wrap) {\r\n        _backgroundWidth = surface.w;\r\n        _backgroundHeight = surface.h;\r\n    \r\n        if (destinationX > 0) { \r\n            \/\/ Move destinationX to 0\r\n            subRectX = surface.w - destinationX;\r\n            destinationX = 0;\r\n        }\r\n\r\n        if (destinationY > 0) {\r\n            \/\/ Move destinationY to 0\r\n            subRectX = surface.w - destinationX;\r\n            destinationY = 0;\r\n        }\r\n    }\r\n\r\n    \/\/ Clip subRect to working window bounds\r\n    Common::Rect subRect(subRectX, subRectY, subRectX + _workingWidth, subRectY + _workingHeight);\r\n\r\n    if (!wrap) {\r\n        \/\/ Clip to image bounds\r\n        subRect.clip(surface.w, surface.h);\r\n    }\r\n\r\n    \/\/ Check destRect for validity\r\n    if (!subRect.isValidRect() || subRect.isEmpty())\r\n        return;\r\n\r\n    if (_renderTable.getRenderState() == RenderTable::FLAT) {\r\n        _system->copyRectToScreen(surface.getBasePtr(subRect.left, subRect.top), surface.pitch, destinationX + _workingWindow.left, destinationY + _workingWindow.top, subRect.width(), subRect.height());\r\n    } else {\r\n        _renderTable.mutateImage((uint16 *)surface.getPixels(), _workingWindowBuffer, surface.w, surface.h, destinationX, destinationY, subRect, wrap);\r\n\r\n        _system->copyRectToScreen(_workingWindowBuffer, _workingWidth * sizeof(uint16), destinationX + _workingWindow.left, destinationY + _workingWindow.top, subRect.width(), subRect.height());\r\n    }\r\n}\r\n<\/pre>\n
          So to walk through it:<\/p>\n
            \n
          1. If destinationX\/Y is less than 0, the image is off the screen to the left\/top. Therefore get the top left corner of the subRect by\u00a0subtracting\u00a0<\/i>destinationX\/Y.<\/li>\n
          2. If destinationX\/Y is greater than the image width\/height respectively, the image is off the screen to the right\/bottom.\u00a0Therefore get the top left corner of the subRect by\u00a0adding\u00a0<\/i>destinationX\/Y.<\/li>\n
          3. If we’re wrapping and destinationX\/Y is still positive at this point, it means that the image will be rendered like this:\n
            <\/div>\n<\/li>\n
          4. We want it to fully wrap, so we offset the image to the left one imageWidth, and then let mutateImage() take care of actually wrapping.<\/li>\n<\/ol>\n
            The last change to the render system was not due to a problem with the system, but due to a problem with the pixel format of the images. All images in Zork Nemesis and Zork Grand Inquisitor are encoded in RGB 555. However, a few of the ScummVM backends do not support RGB 555. Therefore, it was desirable to convert all images to RGB 565 on the fly. To do this, all image pixel data is first loaded into a Surface, then converted to RGB 565. After that, it is passed to renderSubRectToSurface().<\/p>\n
            Since I was alreadly preloading the pixel data into a Surface for RGB conversion, I figured that was a good place to do ‘un-transpose-ing’, rather than having to do it within mutateImage().<\/p>\n
            So, with all the changes, this is the current state of the render system:<\/p>\n
              \n
            1. Read image pixel data from file and dump it into a Surface buffer. In the case of a background image, the surface buffer is stored so we only have to read the file once.\n
              void RenderManager::readImageToSurface(const Common::String &fileName, Graphics::Surface &destination) {\r\n    Common::File file;\r\n\r\n    if (!file.open(fileName)) {\r\n        warning(\"Could not open file %s\", fileName.c_str());\r\n        return;\r\n    }\r\n\r\n    \/\/ Read the magic number\r\n    \/\/ Some files are true TGA, while others are TGZ\r\n    uint32 fileType = file.readUint32BE();\r\n\r\n    uint32 imageWidth;\r\n    uint32 imageHeight;\r\n    Graphics::TGADecoder tga;\r\n    uint16 *buffer;\r\n    bool isTransposed = _renderTable.getRenderState() == RenderTable::PANORAMA;\r\n    \/\/ All ZEngine images are in RGB 555\r\n    Graphics::PixelFormat pixelFormat555 = Graphics::PixelFormat(2, 5, 5, 5, 0, 10, 5, 0, 0);\r\n    destination.format = pixelFormat555;\r\n\r\n    bool isTGZ;\r\n\r\n    \/\/ Check for TGZ files\r\n    if (fileType == MKTAG('T', 'G', 'Z', '\\0')) {\r\n        isTGZ = true;\r\n\r\n        \/\/ TGZ files have a header and then Bitmap data that is compressed with LZSS\r\n        uint32 decompressedSize = file.readSint32LE();\r\n        imageWidth = file.readSint32LE();\r\n        imageHeight = file.readSint32LE();\r\n\r\n        LzssReadStream lzssStream(&file);\r\n        buffer = (uint16 *)(new uint16[decompressedSize]);\r\n        lzssStream.read(buffer, decompressedSize);\r\n    } else {\r\n        isTGZ = false;\r\n\r\n        \/\/ Reset the cursor\r\n        file.seek(0);\r\n\r\n        \/\/ Decode\r\n        if (!tga.loadStream(file)) {\r\n            warning(\"Error while reading TGA image\");\r\n            return;\r\n        }\r\n\r\n        Graphics::Surface tgaSurface = *(tga.getSurface());\r\n        imageWidth = tgaSurface.w;\r\n        imageHeight = tgaSurface.h;\r\n\r\n        buffer = (uint16 *)tgaSurface.getPixels();\r\n    }\r\n\r\n    \/\/ Flip the width and height if transposed\r\n    if (isTransposed) {\r\n        uint16 temp = imageHeight;\r\n        imageHeight = imageWidth;\r\n        imageWidth = temp;\r\n    }\r\n\r\n    \/\/ If the destination internal buffer is the same size as what we're copying into it,\r\n    \/\/ there is no need to free() and re-create\r\n    if (imageWidth != destination.w || imageHeight != destination.h) {\r\n        destination.create(imageWidth, imageHeight, pixelFormat555);\r\n    }\r\n\r\n    \/\/ If transposed, 'un-transpose' the data while copying it to the destination\r\n    \/\/ Otherwise, just do a simple copy\r\n    if (isTransposed) {\r\n        uint16 *dest = (uint16 *)destination.getPixels();\r\n\r\n        for (uint32 y = 0; y < imageHeight; y++) {\r\n            uint32 columnIndex = y * imageWidth;\r\n\r\n            for (uint32 x = 0; x < imageWidth; x++) {\r\n                dest[columnIndex + x] = buffer[x * imageHeight + y];\r\n            }\r\n        }\r\n    } else {\r\n        memcpy(destination.getPixels(), buffer, imageWidth * imageHeight * _pixelFormat.bytesPerPixel);\r\n    }\r\n\r\n    \/\/ Cleanup\r\n    if (isTGZ) {\r\n        delete[] buffer;\r\n    } else {\r\n        tga.destroy();\r\n    }\r\n\r\n    \/\/ Convert in place to RGB 565 from RGB 555\r\n    destination.convertToInPlace(_pixelFormat);\r\n}\r\n<\/pre>\n<\/li>\n
            2. Use the ScriptManager to calculate the destination coordinates<\/li>\n
            3. Call renderSubRectToScreen(surface, destinationX, destinationY, wrap) \u00a0 \u00a0(see above)\n
                \n
              1. If destinationX\/Y is less than 0, the image is off the screen to the left\/top. Therefore get the top left corner of the subRect by\u00a0subtracting\u00a0<\/i>destinationX\/Y.<\/li>\n
              2. If destinationX\/Y is greater than the image width\/height respectively, the image is off the screen to the right\/bottom.\u00a0Therefore get the top left corner of the subRect by\u00a0adding\u00a0<\/i>destinationX\/Y.<\/li>\n
              3. If we’re wrapping and destinationX\/Y is still positive at this point,\u00a0offset the image to the left one imageWidth<\/li>\n
              4. If we’re in PANORAMA or TILT state, call mutateImage() \u00a0 \u00a0 (see above)\n
                  \n
                1. Iterate over the pixels of the subRect<\/li>\n
                2. At each pixel get the coordinate offsets from the RenderTable<\/li>\n
                3. Add the offsets to the coordinates of the pixel.<\/li>\n
                4. Use these new coordinates to get the location of the pixel color<\/li>\n
                5. Store this color at the coordinates of the original pixel<\/li>\n<\/ol>\n<\/li>\n
                6. Blit the final result to the Screen using OSystem::copyRectToScreen()<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
                  That’s it! Thanks for reading. As always, feel free to ask questions or make comments. Happy coding!<\/p>\n
                  -RichieSams<\/p>\n","protected":false},"excerpt":{"rendered":"
                  Over the course of this project, the way I’ve rendered images to the screen has rather drastically changed. Well, let me clarify. Everything is blitted to the screen in exactly the same way ( OSystem::copyRectToScreen ), however, how I get\/modify the pixels that I pass to copyRectToScreen() has changed. (Disclaimer: From past experiences, we know […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-40","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/posts\/40","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/comments?post=40"}],"version-history":[{"count":1,"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/posts\/40\/revisions"}],"predecessor-version":[{"id":49,"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/posts\/40\/revisions\/49"}],"wp:attachment":[{"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/media?parent=40"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/categories?post=40"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/richiesams\/wp-json\/wp\/v2\/tags?post=40"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}