基于笔刷的交互式元素填充技术

doi:10.11996/JG.j.2095-302X.2025010188

图学学报 ›› 2025, Vol. 46 ›› Issue (1): 188-199.DOI: 10.11996/JG.j.2095-302X.2025010188

• 计算机图形学与虚拟现实 • 上一篇下一篇

基于笔刷的交互式元素填充技术

梁沐(), 徐鹏飞(), 黄惠

深圳大学可视计算研究中心，广东深圳 518060

收稿日期:2024-07-08 接受日期:2024-10-31 出版日期:2025-02-28 发布日期:2025-02-14
通讯作者:徐鹏飞(1986-)，男，副教授，博士。主要研究方向为计算机图形学、人机交互等。E-mail：xupengfei.cg@gmail.com
第一作者:梁沐(1997-)，男，硕士研究生。主要研究方向为计算机图形学。E-mail：liangmu0311@gmail.com
基金资助:
国家自然科学基金(62072316);广东省自然科学基金(2023A1515011297);广东高等学校创新团队项目(2022KCXTD025);深圳大学教学改革项目(JG2024018);深圳大学教学改革项目(SZUGS2022JG01)

Brush-based interactive element packing

LIANG Mu(), XU Pengfei(), HUANG Hui

Visual Computing Research Center, Shenzhen University, Shenzhen Guangdong 518060, China

Received:2024-07-08 Accepted:2024-10-31 Published:2025-02-28 Online:2025-02-14
Contact: XU Pengfei (1986-), associate professor, Ph.D. His main research interests cover computer graphics, human-computer interaction, etc. E-mail：xupengfei.cg@gmail.com
First author：LIANG Mu (1997-), master student. His main research interest covers computer graphics. E-mail：liangmu0311@gmail.com
Supported by:
National Natural Science Foundation of China(62072316);Natural Science Foundation of Guangdong Province(2023A1515011297);DEGP Innovation Team(2022KCXTD025);Shenzhen University Key Teaching Reform Project(JG2024018);Shenzhen University Key Teaching Reform Project(SZUGS2022JG01)

摘要/Abstract

摘要：

元素填充是一种将多个元素紧密填充到某个区域的视觉艺术形式，广泛应用于标志、艺术作品、海报和广告设计。在进行元素填充设计时，需要手动地将元素调整到合适的大小和方向，设计过程重复且耗时。现有的元素填充算法可以帮助设计师快速对元素进行排列。使用这些算法将设计过程分为2步，即首先指定填充区域，再进行元素填充。而在实际创作中，元素的排列与填充区域的确定是同时进行的。因此现有的算法与设计过程不适配。采用易于使用的笔刷作为交互工具，实现拟定边界的同时完成填充。提出了一种基于笔刷和物理模拟的元素填充技术，每个元素都由三角形网格表示并应用于一个弹簧质量系统。通过物理模拟使不重叠的元素相互吸引，重叠的元素相互排斥，达到紧凑填充的目标。与常用于颜色填充的传统笔刷的使用方式类似，笔刷能够实时地完成元素填充。通过邀请多位用户使用本文的系统完成设计任务，验证了该方法在大大减少设计耗时的同时，可显著提高设计过程中的可控性和填充结果的紧凑性。

关键词: 元素填充, 笔刷设计, 物理模拟, 实时变形, 图形设计

Abstract:

Element packing is a visual art form that involves tightly packing elements within an area, often seen in logos and art-works, particularly in posters and advertisements. The traditional process of designing element packing requires manual adjustments to align elements to the appropriate size and orientation, which is repetitive and time-consuming. Existing algorithms can assist designers in quickly designing by dividing the design process into two steps: outlining the packing area then packing the elements. However, in actual creative workflows, these two steps occur simultaneously. Therefore, existing methods are incompatible with the real design process. To address this issue, an easy-to-use brush tool was introduced to achieve packing while outlining boundaries. A brush-based element packing technique was proposed, where each element was represented as a triangle mesh and applied to a spring mass system. During simulation, non-overlapping elements were attracted to each other, while overlapping elements repelled each other. Similar to traditional brushes used for color filling, the brush tool allows real-time element packing. By inviting multiple users to design using the system, the effectiveness of the proposed method was evaluated. Results indicated that the technique significantly reduced design time, improved compactness of packing results, and enhanced controllability of the process.

Key words: element packing, brush design, physical simulation, real-time deformation, graphics design

中图分类号:

TP391.41

梁沐, 徐鹏飞, 黄惠. 基于笔刷的交互式元素填充技术[J]. 图学学报, 2025, 46(1): 188-199.

LIANG Mu, XU Pengfei, HUANG Hui. Brush-based interactive element packing[J]. Journal of Graphics, 2025, 46(1): 188-199.

图/表 18

图1 元素填充设计

Fig. 1 Element packing design

图2 从左至右：长颈鹿经过旋转后变成企鹅[10]

Fig. 2 From left to right: giraffes turn into penguins after being rotated[10]

图3 元素示意图((a)路径示意图(J=5)；(b)色块示意图(K=3))

Fig. 3 Sketch map ((a) Path (J=5); (b) Color blocks (K=3))

图4 三角网格T (绿色实线)与辅助边(黑色虚线)

Fig. 4 Triangle Mesh T (green solid line) and auxiliary (black dashed line)

图5 受力示意图((a)弹力与保形力；(b)斥力；(c)引力；(d)边界力)

Fig. 5 Force diagram ((a) Edge force and shape force; (b) Repulsive force; (c) Attractive force; (d) Boundary force)

图6 同类元素变形前后形状差异最大的2个元素((a)植物；(b)花朵；(c)胡萝卜；(d)圆圈)

Fig. 6 The two elements with the biggest shape difference before and after deformation of the same element ((a) Plant; (b) Flower; (c) Carrot; (d) Circle)

图7 对比实验

Fig. 7 Comparison ((a) Ours; (b) Fillinger; (c) RepulsionPak[14]; (d) AEF[13]+RepulsionPak[14])

表1 图7中各个方法的运算时间对比

Table 1 Computing time of each method in figure 7

方法	运算时间/ms
本文方法	210
Fillinger	8520
RepulsionPak^[14]	28460
AEF^[13]+RepulsionPak^[14]	4910

图8 交叉区域

Fig. 8 Intersection area ((a) Ours; (b) Fillinger; (c) RepulsionPak[14]; (d) AEF[13]+RepulsionPak[14])

图9 负空间示意图与删除后重绘示例((a)左图负空间为0.726，右图负空间为0.717；(b)除笔刷后重绘)

Fig. 9 Negative space and redraw after deleting ((a) Use negative space to measure the packing results (left: 0.726; right: 0.717); (b) Redraw after deleting)

表2 图8，9(a)，11，12的填充指标d的计算数值

Table 2 The calculated values of the filling factor d for Figures 8, 9(a), 11, and 12

图号	d
图8(a)	38.679
图8(b)	136.413
图8(c)	63.284
图8(d)	56.813
图9(a) (left)	58.587
图9(a) (right)	61.225
图11(a)	42.614
图11(b)	51.106
图11(c)	46.563
图11(d)	37.342
图11(e)	49.731
图12(a)	105.299
图12(b)	57.160
图12(c)	79.535
图12(d)	75.082
图12(e)	83.462

图10 消融实验((a)最终结果；(b)缺少弹力；(c)缺少边界力；(d)缺少斥力；(e)缺少引力；(f)缺少保形力)

Fig. 10 Ablation experiment ((a) Result; (b) w/o edge force; (c) w/o boundary force; (d) w/o repulsive force; (e) w/o attractive force; (f) w/o shape force)

图11 用户设计结果((a)设计师；(b)用户1；(c)用户2；(d)用户3；(e)用户4)

Fig. 11 User design ((a) Designer; (b) User 1; (c) User 2; (d) User 3; (e) User 4)

图12 用户设计结果((a)设计师+AEF[13]+RepulsionPak[14]；(b)用户1+AEF[13] + RepulsionPak[14]；(c)用户2+RepulsionPak[14]；(d)用户3+RepulsionPak[14]；(e)用户4+RepulsionPak[14])

Fig. 12 User design ((a) Designer + AEF[13] + RepulsionPak[14]; (b) User 1 + AEF[13] + RepulsionPak[14]; (c) User 2 + RepulsionPak[14]; (d) User 3 + RepulsionPak[14]; (e) User 4 + RepulsionPak[14])

图13 评分结果((a)本文方法(实线)和对照组(虚线)与手动填充设计的相似度评分；(b)综合评分表)

Fig. 13 Score results ((a) Similarity score of our method (solid line) and existed methods (dashed line); (b) Comprehensive scoring)

图14 Hand draw ((a)字体设计；(b)图案设计)

Fig. 14 Hand draw ((a) Font design; (b) Graphic design)

图15 元素填充((a)装饰设计(左为设计师设计，右为本文方法)；(b)简笔画元素填充)

Fig. 15 Element packing ((a) Decoration design (left from designer, right from our method); (b) Stick figure packing)

图16 实时变形((a)凹图形失真变形以及牺牲边界的情况；(b)删除左边图上的左上角凸出的元素)

Fig. 16 Real-time deformation ((a) Concave shape distortion and sacrificial boundary conditions; (b) Delete the element in the upper left corner of the left picture)

参考文献 36

[1]	RAAD L, DAVY A, DESOLNEUX A, et al. A survey of exemplar-based texture synthesis[J]. Annals of Mathematical Sciences and Applications, 2018, 3(1): 89-148.
[2]	TU P H, WEI L Y, YATANI K, et al. Continuous curve textures[J]. ACM Transactions on Graphics (TOG), 2020, 39(6): 168.
[3]	TU P H, WEI L Y, ZWICKER M. Clustered vector textures[J]. ACM Transactions on Graphics (TOG), 2022, 41(4): 159.
[4]	BARLA P, BRESLAV S, THOLLOT J, et al. Stroke pattern analysis and synthesis[J]. Computer Graphics Forum, 2006, 25(3): 663-671.
[5]	LUKÁČ M, FIŠER J, ASENTE P, et al. Brushables: example‐based edge‐aware directional texture painting[J]. Computer Graphics Forum, 2015, 34(7): 257-267.
[6]	KAZI R H, IGARASHI T, ZHAO S D, et al. Vignette: interactive texture design and manipulation with freeform gestures for pen-and-ink illustration[C]// SIGCHI Conference on Human Factors in Computing Systems. New York: ACM, 2012: 1727-1736.
[7]	LI Y F, BREEN D E, MCCANN J, et al. Algorithmic quilting pattern generation for pieced quilts[C]// The 45th Graphics Interface Conference. New York: ACM, 2019: 13.
[8]	LU J W, BARNES C, WAN C, et al. DecoBrush: drawing structured decorative patterns by example[J]. ACM Transactions on Graphics (TOG), 2014, 33(4): 90.
[9]	ALBANO V, FANNI F A, GIACHETTI A, et al. FloralSurf: space-filling geodesic ornaments[EB/OL]. [2024-03-08]. https://diglib.eg.org/items/26dc8a7b-a842-4f33-b6be-a34c6e6a9575.
[10]	SAPUTRA R A, KAPLAN C S, ASENTE P. Improved deformation-driven element packing with RepulsionPak[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(4): 2396-2408.
[11]	KWAN K C, SINN L T, HAN C, et al. Pyramid of arclength descriptor for generating collage of shapes[J]. ACM Transactions on Graphics (TOG), 2016, 35(6): 229.
[12]	HSU C Y, WEI L Y, YOU L H, et al. Brushing element fields[C]// The SIGGRAPH Asia 2018 Technical Briefs. New York: ACM, 2018: 6.
[13]	HSU C Y, WEI L Y, YOU L H, et al. Autocomplete element fields[C]// The 2020 CHI Conference on Human Factors in Computing Systems. New York: ACM, 2020: 1-13.
[14]	SAPUTRA R A, KAPLAN C S, ASENTE P, et al. RepulsionPak: deformation-driven element packing with repulsion forces[C]// The 44th Graphics Interface Conference. Waterloo: Canadian Human-Computer Communications Society, 2018: 10-17.
[15]	陈中贵, 欧阳永昇, 曹娟. 特征保持的马赛克图像生成方法[J]. 计算机辅助设计与图形学学报, 2014, 26(4): 520-527.
	CHEN Z G, OUYANG Y S, CAO J. Feature-preserving method for mosaic image generation[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(4): 520-527 (in Chinese).
[16]	XU P F, DING J Q, ZHANG H, et al. Discernible image mosaic with edge-aware adaptive tiles[J]. Computational Visual Media, 2019, 5(1): 45-58.
[17]	杨祖义, 张俊松. 融合主题和视觉特征的图片拼贴画合成方法[J]. 计算机辅助设计与图形学学报, 2019, 31(8): 1403-1409.
	YANG Z Y, ZHANG J S. Picture collage synthesis considering theme and visual features[J]. Journal of Computer-Aided Design & Computer Graphics, 2019, 31(8): 1403-1409 (in Chinese).
[18]	KIM J, PELLACINI F. Jigsaw image mosaics[J]. ACM Transactions on Graphics (TOG), 2002, 21(3): 657-664.
[19]	HAUSNER A. Simulating decorative mosaics[C]// The 28th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2001: 573-580.
[20]	SMITH K, LIU Y J, KLEIN A. Animosaics[C]// The 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM, 2005: 201-208.
[21]	CHEN M H, XU F, LU L. Manufacturable pattern collage along a boundary[J]. Computational Visual Media, 2019, 5(3): 293-302.
[22]	余丽娟, 曹娟, 陈中贵. 改进区域划分的圆Packing变分算法[J]. 计算机辅助设计与图形学学报, 2018, 30(7): 1251-1257.
	YU L J, CAO J, CHEN Z G. Improved domain partitions for variational circle packing[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(7): 1251-1257 (in Chinese).
[23]	刘景发, 张国建, 刘文杰, 等. 正三角形容器内等圆Packing问题的启发式算法[J]. 计算机辅助设计与图形学学报, 2012, 24(6): 808-815.
	LIU J F, ZHANG G J, LIU W J, et al. Heuristic algorithm for the equal circles packing problem in equilateral triangle container[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(6): 808-815 (in Chinese).
[24]	张凯, 柯颖, 曹娟, 等. 圆组填充算法驱动的平面马赛克模拟[J]. 计算机辅助设计与图形学学报, 2018, 30(7): 1216-1223.
	ZHANG K, KE Y, CAO J, et al. Circle group packing algorithm for mosaic synthesis[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(7): 1216-1223 (in Chinese).
[25]	GIESEKE L, ASENTE P, LU J W, et al. Organized order in ornamentation[C]// The Symposium on Computational Aesthetics. New York: ACM, 2017: 4.
[26]	REINERT B, RITSCHEL T, SEIDEL H P. Interactive by-example design of artistic packing layouts[J]. ACM Transactions on Graphics (TOG), 2013, 32(6): 218.
[27]	DAVISON T, SAMAVATI F, JACOB C. Interactive example-palettes for discrete element texture synthesis[J]. Computers & Graphics, 2019, 78: 23-36.
[28]	张驰, 张效娟, 赵洋, 等. 基于调色板的半交互式低照度唐卡图像增强[J]. 图学学报, 2023, 44(6): 1202-1211. DOI
	ZHANG C, ZHANG X J, ZHAO Y, et al. Palette-based semi-interactive low-light Thangka images enhancement[J]. Journal of Graphics, 2023, 44(6): 1202-1211 (in Chinese). DOI
[29]	王华, 李绅绅, 何晓宇, 等. 基于个性化定制的交互式蒙版擦除动画设计与实现[J]. 图学学报, 2019, 40(3): 473-480. DOI
	WANG H, LI S S, HE X Y, et al. Design and implementation of interactive mask erasing animation based on personalized customization[J]. Journal of Graphics, 2019, 40(3): 473-480 (in Chinese). DOI
[30]	BENES B, ZHOU X C, CHANG P, et al. Urban brush: intuitive and controllable urban layout editing[C]// The 34th Annual ACM Symposium on User Interface Software and Technology. New York: ACM, 2021: 796-814.
[31]	SAPUTRA R A, KAPLAN C S, ASENTE P, et al. FLOWPAK: flow-based ornamental element packing[C]// The 43rd Graphics Interface Conference. Waterloo: Canadian Human-Computer Communications Society, 2017: 8-15.
[32]	NICOLET B, ECORMIER-NOCCA P, MEMARI P, et al. Pair correlation functions with free-form boundaries for distribution inpainting and decomposition[EB/OL]. [2024-03-08]. https://inria.hal.science/hal-02500803/file/short1039_CRC.pdf.
[33]	NIETO J R, SUSÍN A. Cage based deformations: a survey[M]//HIDALGO M G, TORRES A M, GÓMEZ J V. Deformation Models: Tracking, Animation and Applications. Dordrecht: Springer, 2013: 75-99.
[34]	ZHANG J Y, DENG B L, LIU Z S, et al. Local barycentric coordinates[J]. ACM Transactions on Graphics (TOG), 2014, 33(6): 188.
[35]	JACOBSON A, BARAN I, POPOVIĆ J, et al. Bounded biharmonic weights for real-time deformation[J]. ACM Transactions on Graphics (TOG), 2011, 30(4): 78.
[36]	FLOATER M S. Mean value coordinates[J]. Computer Aided Geometric Design, 2003, 20(1): 19-27.

基于笔刷的交互式元素填充技术

Brush-based interactive element packing

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 18

参考文献 36

相关文章 1

编辑推荐

Metrics

本文评价