| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2000-2022 Inria | ||
| 3 | * All rights reserved. | ||
| 4 | * | ||
| 5 | * Redistribution and use in source and binary forms, with or without | ||
| 6 | * modification, are permitted provided that the following conditions are met: | ||
| 7 | * | ||
| 8 | * * Redistributions of source code must retain the above copyright notice, | ||
| 9 | * this list of conditions and the following disclaimer. | ||
| 10 | * * Redistributions in binary form must reproduce the above copyright notice, | ||
| 11 | * this list of conditions and the following disclaimer in the documentation | ||
| 12 | * and/or other materials provided with the distribution. | ||
| 13 | * * Neither the name of the ALICE Project-Team nor the names of its | ||
| 14 | * contributors may be used to endorse or promote products derived from this | ||
| 15 | * software without specific prior written permission. | ||
| 16 | * | ||
| 17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
| 18 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
| 19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
| 20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | ||
| 21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
| 22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
| 23 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
| 24 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
| 25 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
| 26 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
| 27 | * POSSIBILITY OF SUCH DAMAGE. | ||
| 28 | * | ||
| 29 | * Contact: Bruno Levy | ||
| 30 | * | ||
| 31 | * https://www.inria.fr/fr/bruno-levy | ||
| 32 | * | ||
| 33 | * Inria, | ||
| 34 | * Domaine de Voluceau, | ||
| 35 | * 78150 Le Chesnay - Rocquencourt | ||
| 36 | * FRANCE | ||
| 37 | * | ||
| 38 | */ | ||
| 39 | |||
| 40 | #include <geogram/image/image_rasterizer.h> | ||
| 41 | #include <stack> | ||
| 42 | |||
| 43 | namespace GEO { | ||
| 44 | |||
| 45 | ✗ | ImageRasterizer::ImageRasterizer( | |
| 46 | Image* image | ||
| 47 | ✗ | ) : image_(image) { | |
| 48 | ✗ | component_encoding_ = image_->component_encoding(); | |
| 49 | ✗ | nb_components_ = index_t( | |
| 50 | ✗ | Image::nb_components(image_->color_encoding()) | |
| 51 | ); | ||
| 52 | ✗ | } | |
| 53 | |||
| 54 | ✗ | void ImageRasterizer::clear() { | |
| 55 | ✗ | Memory::clear(image_->base_mem(), image_->bytes()); | |
| 56 | ✗ | } | |
| 57 | |||
| 58 | ✗ | void ImageRasterizer::triangle( | |
| 59 | const vec2i& P1, const Color& c1, | ||
| 60 | const vec2i& P2, const Color& c2, | ||
| 61 | const vec2i& P3, const Color& c3 | ||
| 62 | ) { | ||
| 63 | // Find triangle's bounding box. | ||
| 64 | ✗ | int xmin = std::min(P1.x,std::min(P2.x,P3.x)); | |
| 65 | ✗ | int ymin = std::min(P1.y,std::min(P2.y,P3.y)); | |
| 66 | ✗ | int xmax = std::max(P1.x,std::max(P2.x,P3.x)); | |
| 67 | ✗ | int ymax = std::max(P1.y,std::max(P2.y,P3.y)); | |
| 68 | |||
| 69 | ✗ | geo_clamp(xmin, 0, int(image_->width()-1)); | |
| 70 | ✗ | geo_clamp(xmax, 0, int(image_->width()-1)); | |
| 71 | ✗ | geo_clamp(ymin, 0, int(image_->height()-1)); | |
| 72 | ✗ | geo_clamp(ymax, 0, int(image_->height()-1)); | |
| 73 | |||
| 74 | ✗ | int D = (P2.x - P1.x) * (P3.y - P1.y) - (P2.y - P1.y) * (P3.x - P1.x); | |
| 75 | |||
| 76 | ✗ | if(D == 0) { | |
| 77 | ✗ | return; | |
| 78 | } | ||
| 79 | |||
| 80 | // Iterative computation of barycentric coordinates. | ||
| 81 | |||
| 82 | ✗ | int cxl1 = P2.y - P3.y; | |
| 83 | ✗ | int cxl2 = P3.y - P1.y; | |
| 84 | ✗ | int cxl3 = P1.y - P2.y; | |
| 85 | |||
| 86 | ✗ | int cyl1 = P3.x - P2.x; | |
| 87 | ✗ | int cyl2 = P1.x - P3.x; | |
| 88 | ✗ | int cyl3 = P2.x - P1.x; | |
| 89 | |||
| 90 | ✗ | int c0l1 = P2.x*P3.y-P3.x*P2.y; | |
| 91 | ✗ | int c0l2 = P3.x*P1.y-P1.x*P3.y; | |
| 92 | ✗ | int c0l3 = P1.x*P2.y-P2.x*P1.y; | |
| 93 | |||
| 94 | ✗ | int row_l1 = xmin * cxl1 + ymin * cyl1 + c0l1; | |
| 95 | ✗ | int row_l2 = xmin * cxl2 + ymin * cyl2 + c0l2; | |
| 96 | ✗ | int row_l3 = xmin * cxl3 + ymin * cyl3 + c0l3; | |
| 97 | |||
| 98 | ✗ | for(int y=ymin; y<ymax; ++y) { | |
| 99 | ✗ | int l1 = row_l1; | |
| 100 | ✗ | int l2 = row_l2; | |
| 101 | ✗ | int l3 = row_l3; | |
| 102 | ✗ | for(int x=xmin; x<xmax; ++x) { | |
| 103 | ✗ | if( | |
| 104 | ✗ | (D > 0 && l1 >= 0.0 && l2 >= 0.0 && l3 >= 0.0) || | |
| 105 | ✗ | (D < 0 && l1 <= 0.0 && l2 <= 0.0 && l3 <= 0.0) | |
| 106 | ) { | ||
| 107 | ✗ | Color c; | |
| 108 | ✗ | interpolate_color( | |
| 109 | c1,c2,c3, | ||
| 110 | ✗ | double(l1)/double(D), | |
| 111 | ✗ | double(l2)/double(D), | |
| 112 | ✗ | double(l3)/double(D), | |
| 113 | c | ||
| 114 | ); | ||
| 115 | ✗ | set_pixel(x,y,c); | |
| 116 | } | ||
| 117 | ✗ | l1 += cxl1; | |
| 118 | ✗ | l2 += cxl2; | |
| 119 | ✗ | l3 += cxl3; | |
| 120 | } | ||
| 121 | ✗ | row_l1 += cyl1; | |
| 122 | ✗ | row_l2 += cyl2; | |
| 123 | ✗ | row_l3 += cyl3; | |
| 124 | } | ||
| 125 | } | ||
| 126 | |||
| 127 | |||
| 128 | ✗ | void ImageRasterizer::segment( | |
| 129 | const vec2i& P1, const vec2i& P2, const Color& c | ||
| 130 | ) { | ||
| 131 | // Bresenham line drawing | ||
| 132 | ✗ | int dy = int(P2.y - P1.y); | |
| 133 | ✗ | int sy = 1; | |
| 134 | ✗ | if(dy < 0) { | |
| 135 | ✗ | sy = -1; | |
| 136 | ✗ | dy = -dy; | |
| 137 | } | ||
| 138 | |||
| 139 | ✗ | int dx = int(P2.x - P1.x); | |
| 140 | ✗ | int sx = 1; | |
| 141 | ✗ | if(dx < 0) { | |
| 142 | ✗ | sx = -1; | |
| 143 | ✗ | dx = -dx; | |
| 144 | } | ||
| 145 | |||
| 146 | ✗ | int x = int(P1.x); | |
| 147 | ✗ | int y = int(P1.y); | |
| 148 | ✗ | if(dy > dx) { | |
| 149 | ✗ | int ex = (dx << 1) - dy; | |
| 150 | ✗ | for(int u=0; u<dy; u++) { | |
| 151 | ✗ | set_pixel(x,y,c); | |
| 152 | ✗ | y += sy; | |
| 153 | ✗ | while(ex >= 0) { | |
| 154 | ✗ | set_pixel(x,y,c); | |
| 155 | ✗ | x += sx; | |
| 156 | ✗ | ex -= dy << 1; | |
| 157 | } | ||
| 158 | ✗ | ex += dx << 1; | |
| 159 | } | ||
| 160 | } else { | ||
| 161 | ✗ | int ey = (dy << 1) - dx; | |
| 162 | ✗ | for(int u=0; u<dx; u++) { | |
| 163 | ✗ | set_pixel(x,y,c); | |
| 164 | ✗ | x += sx; | |
| 165 | ✗ | while(ey >= 0) { | |
| 166 | ✗ | set_pixel(x,y,c); | |
| 167 | ✗ | y += sy; | |
| 168 | ✗ | ey -= dx << 1; | |
| 169 | } | ||
| 170 | ✗ | ey += dy << 1; | |
| 171 | } | ||
| 172 | } | ||
| 173 | ✗ | } | |
| 174 | |||
| 175 | ✗ | void ImageRasterizer::fillcircle( | |
| 176 | const vec2i& C, int R, const Color& c | ||
| 177 | ) { | ||
| 178 | // TODO if need be: more efficient algorithm using | ||
| 179 | // Bresenham for circles | ||
| 180 | |||
| 181 | ✗ | int x1 = std::max(C.x-R,0); | |
| 182 | ✗ | int y1 = std::max(C.y-R,0); | |
| 183 | ✗ | int x2 = std::min(C.x+R,int(image_->width()-1)); | |
| 184 | ✗ | int y2 = std::min(C.y+R,int(image_->height()-1)); | |
| 185 | |||
| 186 | ✗ | for(int y=y1; y<y2; ++y) { | |
| 187 | ✗ | for(int x=x1; x<x2; ++x) { | |
| 188 | ✗ | if((x-C.x)*(x-C.x)+(y-C.y)*(y-C.y) <= R*R) { | |
| 189 | ✗ | set_pixel(x,y,c); | |
| 190 | } | ||
| 191 | } | ||
| 192 | } | ||
| 193 | ✗ | } | |
| 194 | |||
| 195 | ✗ | void ImageRasterizer::flood_fill(int x, int y, const Color& c) { | |
| 196 | // TODO if need be: more efficient flood fill using scanline | ||
| 197 | ✗ | if(!pixel_is_black(x,y)) { | |
| 198 | ✗ | return; | |
| 199 | } | ||
| 200 | ✗ | std::stack<vec2i> S; | |
| 201 | ✗ | set_pixel(x,y,c); | |
| 202 | ✗ | S.push(vec2i(x,y)); | |
| 203 | ✗ | while(!S.empty()) { | |
| 204 | ✗ | vec2i p = S.top(); | |
| 205 | ✗ | S.pop(); | |
| 206 | ✗ | if(p.x > 0 && pixel_is_black(p.x-1,p.y)) { | |
| 207 | ✗ | set_pixel(p.x-1,p.y,c); | |
| 208 | ✗ | S.push(vec2i(p.x-1,p.y)); | |
| 209 | } | ||
| 210 | ✗ | if(p.x < int(image_->width()-1) && pixel_is_black(p.x+1,p.y)) { | |
| 211 | ✗ | set_pixel(p.x+1,p.y,c); | |
| 212 | ✗ | S.push(vec2i(p.x+1,p.y)); | |
| 213 | } | ||
| 214 | ✗ | if(p.y > 0 && pixel_is_black(p.x,p.y-1)) { | |
| 215 | ✗ | set_pixel(p.x,p.y-1,c); | |
| 216 | ✗ | S.push(vec2i(p.x,p.y-1)); | |
| 217 | } | ||
| 218 | ✗ | if(p.y < int(image_->height()-1) && pixel_is_black(p.x,p.y+1)) { | |
| 219 | ✗ | set_pixel(p.x,p.y+1,c); | |
| 220 | ✗ | S.push(vec2i(p.x,p.y+1)); | |
| 221 | } | ||
| 222 | } | ||
| 223 | ✗ | } | |
| 224 | |||
| 225 | } | ||
| 226 |